## 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 =).

It turns out we can do this computation even faster—but that will have to wait for another post! 