Finding the Period of the Decimal Expansion of 1/n

When I was solving Project Euler’s problem 26, I had to find a way to obtain the period of the the decimal expansion of $1/n$ for various integer values of $n$ . I first thought of comparing strings of digits along the decimal expansion to see if they repeated; however, this solution was neither clever nor efficient. With this in mind, I set out to find a better method for this problem.

After some research, I came across something I had never heard about in my high school math classes. The smallest integer exponent $e$ such that $b^e \equiv 1 \ (\textrm{mod} \ n)$ is called the multiplicative order of $b \ (\textrm{mod} \ n)$ .

This value has an interesting property. The multiplicative order of $10 \ (\textrm{mod} \ n)$ is equal to the period of the decimal expansion of $1/n$ . Note that this only works when $n$ is relatively prime to 10, i.e. when $n$ is not divisible by 2 or 5.

Consider a few examples:

n	1/n	Period	Multiplicative Order of 10 (mod n)
$3$	$0. \overline{3}$	$1$	$10^1 \equiv 1 \ (\textrm{mod} \ 3) \therefore e=1$
$7$	$0. \overline{142857}$	$6$	$10^6 \equiv 1 \ (\textrm{mod} \ 7) \therefore e=6$
$9$	$0. \overline{1}$	$1$	$10^1 \equiv 1 \ (\textrm{mod} \ 9) \therefore e=1$
$11$	$0. \overline{09}$	$2$	$10^2 \equiv 1 \ (\textrm{mod} \ 11) \therefore e=2$
$13$	$0. 0\overline{769230}$	$6$	$10^6 \equiv 1 \ (\textrm{mod} \ 13) \therefore e=6$

Honestly, I don’t know why this property works, but it allowed me to solve the problem using an algorithm that was much faster (and clever) than my previous. If you want to look deeper into it, check the links below.

References & Further Resources

Leave a Reply Cancel reply

Archives

Recent Posts

Categories