Finding the repetend length of a decimal expansion

We’re still trying to find the prefix length $k$ and repetend length $n$ of the decimal expansion of a fraction $a/b$ , that is, the length of the part before it starts repeating, and the length of the repeating part. In my previous post we found that the prefix length $k$ is fairly simple to find: it’s equal to the maximum number of factors of either 2 or 5 in $b$ .

What about $n$ ? This is a bit tricker to do efficiently. Let $b'$ denote the result after removing all factors of $2$ or $5$ from $b$ , as before. Then we want $(10^n - 1)$ to be evenly divisible by $b'$ , or put another way, we want the smallest $n$ such that

$10^n \equiv 1 \pmod {b'}.$

So the obvious method is to compute $10 \bmod {b'}$ , $10^2 \bmod {b'}$ , $10^3 \bmod {b'}$ , and so on, and find the first which yields $1$ . Practically speaking, we don’t have to compute $10^n$ from scratch at each step: we can start with $1$ , and then at each step multiply the current value by $10$ and reduce $\pmod {b'}$ . We keep doing this until we reach $1$ again, and record how many steps it took. For example,

$\begin{array}{rcl} 10 &\equiv & 10 \pmod{21} \\ 10 \cdot 10 = 100 &\equiv & 16 \pmod{21} \\ 16 \cdot 10 = 160 &\equiv & 13 \pmod{21} \\ 13 \cdot 10 = 130 &\equiv & 4 \pmod{21} \\ 4 \cdot 10 = 40 &\equiv & 19 \pmod{21} \\ 19 \cdot 10 = 190 &\equiv & 1 \pmod{21} \end{array}$

This took 6 steps, therefore $n = 6$ is the smallest $n$ such that $10^n - 1$ is divisible by 21; this matches what we saw in the previous posts, for example, the fact that $89/420$ has a repetend length of $6$ (remember that removing factors of 2 and 5 from $420$ yields $21$ ).

This method is correct, but we can do better—although for this we’ll need a little bit of group theory!

Recall that $\Phi(b')$ is the set of numbers between $1$ and $b'-1$ (inclusive) which share no common factors with $b'$ .
$\Phi(b')$ actually forms a group under multiplication $\pmod {b'}$ : multiplying two values of $\Phi(b')$ always yields another such value, and for every $x \in \Phi(b')$ there is some $y \in \Phi(b')$ such that $xy \equiv 1 \pmod{b'}$ .
We are then really asking for the order of the element $10$ in the group $\Phi(b')$ .
By Lagrange’s Theorem, the order of an element must evenly divide the order of the group.
The order of a group is just its size; in this case the order of $\Phi(b')$ is $\varphi(b')$ , the Euler totient function of $b'$ .
Hence we have learned that $n$ —the order of $10$ in the group $\Phi(b')$ —must evenly divide $\varphi(b')$ .

We can use this knowledge to find $n$ more quickly than simply counting powers of $10$ : just list all the divisors of $\varphi(b')$ , try each one by raising $10$ to the power of the divisor $\pmod {b'}$ (using fast modular exponentiation of course), and pick the smallest one that yields $1$ . Using our example from before of $b' = 21$ , we find that $\varphi(21) = (3-1)(7-1) = 12$ , and so $n$ has to be one of $1$ , $2$ , $3$ , $4$ , $6$ , or $12$ . As another, bigger example, suppose $b' = 3^5 \cdot 7 \cdot 89 = 151389$ . Then we can compute

$\varphi(b') = (3-1) \cdot 3^4 \cdot (7-1) \cdot (89-1) = 2^5 \cdot 3^5 \cdot 11 = 85536$ .

(I was going to link to an explanation of how to compute $\varphi$ —but it seems although I’ve mentioned $\varphi$ many times before, I’ve never actually written about how to compute it! I’ll have to do that soon, since it’s a very interesting topic. In any case, if you don’t know how, you can just take my word for now.) This number has $6 \cdot 6 \cdot 2 = 72$ divisors we would have to try (since to make a divisor of $2^5 \cdot 3^5 \cdot 11$ , there are $6$ choices for the exponent of $2$ (namely, 0 through 5), 6 choices for the exponent of 3, and 2 choices for the exponent of $11$ ). $72$ things to try is much, much better than trying every single possible value from $1$ up to $151388$ ! I wrote a little computer program to try them all, and it turns out that $n = 1188 = 2^2 \cdot 3^3 \cdot 11^1$ is the smallest divisor that works. Hence, we find that $1/151389$ has a repetend of length $1188$ (but I’m sure you knew that already =).