Repeat Length

Let me go back now to something I said earlier: any denominator can be made special by multiplying by an integer. In other words, any number divides some number of the form 10^j(10^k−1). That's true, but it's a bit too general for me, so let's consider only numbers that contain no factors of two or five, that is, numbers that are relatively prime to 10. Any such number divides some number of the form 10^k−1 … that is, a string of 9s.

No matter how much I think about fractions, it is always amazing and mysterious to me that that's true. I'd like to convey that feeling to you, but if I haven't already, I doubt I'll be able to.

Now, it's pretty easy to see that the fact that any such number divides a string of 9s is equivalent to the fact that decimal expansions eventually repeat. And, that latter fact is easy to prove; in fact I'm going to prove it in just a moment. That puts me in the funny position of saying I don't understand the reason for something, while at the same time having a simple proof of it. But, there it is. I guess it's just one of those cases where the proof doesn't feed back to provide intuition.

Gratuitous quote from The Matrix Reloaded:

But this is not a reason, this is not a “why”.

:

Our only hope, our only peace is to understand it, to understand the “why”. “Why” is what separates us from them, you from me. “Why” is the only real source of power, without it you are powerless. And this is how you come to me, without “why”, without power.

In the rest of this essay, I'll not only show that decimal expansions repeat, but also develop a series of approximate rules about the lengths of the repeating sequences, each coming closer to the actual fact of the matter. That will take me away from plain old numbers into more mathematical realms, but I can't help that.

If you look at the tables of expansions of 1/n that I made for base 10 and base 2, you'll notice that some expansions are much longer than others, and that the longest ones have length n−1. That number suggests the following argument.

When you're doing long division to work out an expansion, there are only so many possible remainders, so one is bound to occur again sooner or later. When that happens, the sequence will repeat. So, the number of digits in the sequence is limited by the number of possible remainders on division by n, which is just n. Or, rather, n−1, because if remainder zero ever occurs, the sequence terminates.

So, that's the first rule, that the length is less than or equal to n−1. As a result, if an expansion has length n−1, it makes sense to say that it has full length.

If you look at the tables, you'll probably also notice that the expansions with full length all have prime denominators (but not vice versa). That suggests that prime denominators might be interesting to look at.

With that in mind, let's go back to long division again, and imagine computing the expansion of m/n, where 0 < m < n. (We don't need to assume that n is prime, yet.) How does it go? First we observe that n doesn't go into m, so m is the remainder, and is carried up to above the first zero. So, next, we see how many times n goes into m×10. The quotient q is the first digit of the expansion, and the remainder r is carried up to above the next zero. And so on.

Now, here's the thing. Almost by definition, the remainder r is congruent to m×10 mod n. So, when we carry it up to above the next zero, to form r×10, that number is congruent to m×10², as is the next remainder. And so on. In other words, if we ignore those pesky quotient digits that we usually think of as the answer, what we're really doing is computing powers of 10 mod n.

Now suppose the expansion repeats with length k. What that means is, for some number i, the remainder at position i+k is the same as the remainder at position i. In other words, we have the congruence

m×10^i+k ≡ m×10ⁱ mod n.

Now let's assume that n is prime, and also that it's not 2 or 5. In that case, m is relatively prime to n, since it's less than n, and also 10 is relatively prime to n, so we can cancel the common factors from both sides to obtain

10^k ≡ 1 mod n.

Now we have to leap into group theory. If you're not familiar with that, all I can say is that everything I'll be doing is very basic, so if you're interested, it would be easy to learn. (The book I learned it from is Topics in Algebra.)

In terms of group theory, what we're looking at is the group of integers under multiplication mod n, and what the previous equation means is that the length of the repeating sequence is equal to the order of the element 10, or, equivalently, to the size of the subgroup generated by 10. By Lagrange's theorem, though, the size of any subgroup divides the size of the group, which is n−1.

So, that's the second rule, that when n is a prime other than 2 or 5, the length is not only less than or equal to n−1, it's a divisor of it. It's also pretty easy to show that there are no digits before the repeating sequence.

We didn't actually need to invoke group theory there. There's a result in number theory, Fermat's (non-last) theorem, that would have given me what I needed. (See, for example, Introduction to Number Theory.) But, it would still be a result most people wouldn't recognize, and anyway that's not how I think of it.

Now, finally, let's go back and consider arbitrary values of n. The first thing we can do is eliminate factors of 2 and 5. If n has a factor of 2, we can multiply both numerator and denominator by 5, and vice versa, so that we get a bunch of factors of 10 in the denominator. Such factors clearly won't affect the repeat length, so we can just ignore them.

So, we can assume that 10 is relatively prime to n. We can also assume that m is relatively prime to n; if it isn't, we can just cancel common factors. Those results bring us right back to the equation 10^k ≡ 1 mod n, only now n is not necessarily a prime. From there, the same result from group theory applies; the only question is, what is the order of the group?

I already wrote a whole essay about just such groups, so I won't say much about them here, I'll just be nice and tell you the answer. To get the order of the group, multiply n by a factor (1 − 1/p) for every prime number p that divides n. The result is known as Euler's function, φ(n).

The third and last rule, then, is that the length divides φ(ñ), where ñ is n, but with factors of 2 and 5 removed. (I'll usually assume that ñ = n, and say that the length divides φ(n).)

Here are some examples where the length doesn't divide n−1. First, φ(21) = 21(1−1/3)(1−1/7) = 12, which fits with the fact that 1/21 repeats (in decimal) with length 6. Second, φ(49) = 49(1−1/7) = 42, which is exactly the repeat length for 1/49.

I discovered some other interesting points, but I'll leave them as exercises. First, compute (for example) the repeat length for 1/21 as a function of the lengths of 1/3 and 1/7. Second, using that result, determine for which n the length can possibly be equal to φ(n), both in base 10 and in general. You might find it instructive to look at 1/22 in base 7.

In case you're wondering … the reason the series of approximate rules doesn't converge to an exact rule is that I don't know one. I suspect that at present, nobody does. To understand why I say that, you have to know one more thing, which is that a primitive root, mod n, is a number that generates the entire group. So, 10 is a primitive root mod n if and only if the decimal expansion of 1/n has length φ(n).

Now, in the book Introduction to Number Theory, which is normally quite terse, there is a table of least primitive roots for all primes less than 5000, with primes for which 10 is a primitive root specially marked. That the author thought this was worthwhile strongly suggests that determining the repeat length is a hard problem.

Actually, speaking of primitive roots and hard problems reminded me of the book Codes and Cryptography, where I found these nice quotes.

Questions about how the primitive roots are distributed, which integers are primitive roots of some prime, and the like are fascinating unanswered questions in number theory.

:

Of more direct interest to the applications we have in mind is the problem of finding primitive roots of an integer n. As far as we know, there is no algorithm known that, given an integer n of (say) N bits, will find a primitive root in time polynomial in N.

So, the problem is hard even in a technical sense. Another interesting fact is that if you have a primitive root, you can not only exponentiate it but also do the inverse, take logarithms with respect to it.

The exponential function defined by (5) is a one-way function.

In other words, we are claiming exponentiation is ‘easy’ but that taking logarithms is ‘hard’.

:

At the moment, there is no known polynomial-time algorithm for computing discrete logarithms, and the difficulty of this computation is commonly regarded as on a par with that of factoring.