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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in computation, group theory, modular arithmetic, number theory, pattern and tagged , , , , , , . Bookmark the permalink.