We’re still trying to find the prefix length and repetend length of the decimal expansion of a fraction , 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 is fairly simple to find: it’s equal to the maximum number of factors of either 2 or 5 in .
What about ? This is a bit tricker to do efficiently. Let denote the result after removing all factors of or from , as before. Then we want to be evenly divisible by , or put another way, we want the smallest such that
So the obvious method is to compute , , , and so on, and find the first which yields . Practically speaking, we don’t have to compute from scratch at each step: we can start with , and then at each step multiply the current value by and reduce . We keep doing this until we reach again, and record how many steps it took. For example,
This took 6 steps, therefore is the smallest such that is divisible by 21; this matches what we saw in the previous posts, for example, the fact that has a repetend length of (remember that removing factors of 2 and 5 from yields ).
This method is correct, but we can do better—although for this we’ll need a little bit of group theory!
- Recall that is the set of numbers between and (inclusive) which share no common factors with .
- actually forms a group under multiplication : multiplying two values of always yields another such value, and for every there is some such that .
- We are then really asking for the order of the element in the group .
- 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 is , the Euler totient function of .
- Hence we have learned that —the order of in the group —must evenly divide .
We can use this knowledge to find more quickly than simply counting powers of : just list all the divisors of , try each one by raising to the power of the divisor (using fast modular exponentiation of course), and pick the smallest one that yields . Using our example from before of , we find that , and so has to be one of , , , , , or . As another, bigger example, suppose . Then we can compute
(I was going to link to an explanation of how to compute —but it seems although I’ve mentioned 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 divisors we would have to try (since to make a divisor of , there are choices for the exponent of (namely, 0 through 5), 6 choices for the exponent of 3, and 2 choices for the exponent of ). things to try is much, much better than trying every single possible value from up to ! I wrote a little computer program to try them all, and it turns out that is the smallest divisor that works. Hence, we find that has a repetend of length (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!