Complementary Parts

Now that you know about the connection between decimal expansions with denominator n and powers of 10 in the group of integers mod n, I can give you a fairly short explanation of why the second half of a repeating sequence is often the first complement of the first half.

It all has to do with the group element −1. So far we've been thinking of the group elements as remainders, so they've all been positive. The wonderful thing about modular arithmetic, though, is that we're free to add and subtract n as much as we please, and all our calculations will turn out just the same in the end. So, the element −1 is really just the remainder n−1 in disguise, but it's a disguise that is much more convenient to work with.

Remember we were interested in the subgroup generated by the element 10? What I'm going to do first is show that if the subgroup contains −1, then the second half of the repeating sequence is the complement of the first half. Then I'll go back and wonder about when the subgroup contains −1.

The first thing to note about the element −1 is that it has order 2. That's easy to see: (−1)² = 1 is true even before we start working mod n. There can be other elements with order 2 as well … for example, 13² ≡ 1 mod 21.

Now, we already know that if the repeating sequence has length k, then the subgroup generated by 10 has k elements, which we can write in a sequence as 10⁰ through 10^k−1. After that, the sequence wraps around, due to the equation

10^k ≡ 1 mod n.

In a sequence like that, the following is true: if k is odd, there is no element with order 2, but if k is even, there is exactly one, namely, the element in the middle of the sequence, 10^k/2. Consequently, if the subgroup contains −1, we know that the length has to be even—a good sign, since we're talking about halves—and that 10^k/2 ≡ −1 mod n.

The sequence of powers of 10 is congruent to the sequence of remainders from long division, so now we can write down the relation between a remainder r₂ in the second half at position (k/2)+i and the corresponding remainder r₁ in the first half at position i.

r₂ ≡ 10^(k/2)+i ≡ 10^k/210ⁱ ≡ (−1)10ⁱ ≡ −10ⁱ ≡ n−10ⁱ ≡ n−r₁ mod n

And, since the remainders can only range from 1 to n−1, the two ends of that relation must be not just congruent but equal: r₂ = n−r₁.

Now, remember how the remainders fit into the process of long division. First we carry the remainder up to above the next zero, giving r×10, then we divide by n to get the next quotient q. So, we can write down the sum of the next quotients as follows.

q₁ + q₂ = r₁×10/n + r₂×10/n = r₁×10/n + (n−r₁)×10/n

The way I've written it, it looks like we could just combine the two terms, then everything would cancel and we'd see that the quotients add up to 10. But, that's not quite right … the quotients are supposed to be integers, so the remainder in each division is lost, and the quotients actually add up to 9. But, the quotients are just the digits of the expansion, and adding up to 9 is what first complements are all about. Q.E.D.

So, that ends the first part of what I wanted to say, that if the element −1 occurs, the halves of the repeating sequence are first complements. The question now is, when does the element −1 occur?

There's one case that is particularly easy to understand: if the expansion has full length, i.e., length n−1, then the subgroup is the whole group, so every element occurs. The same is true if the expansion has length φ(n) … in fact it would be reasonable to call that “full length”, too.

Or, here's another case I thought of. If the group has no other element of order 2, and if the expansion happens to have even length, then the element −1 has to appear in the sequence. Knowing the structure of U_n, you can show that the only values of n for which the group has no other element of order 2 are the prime powers p^d (p ≥ 3, d > 0), the doubled prime powers 2p^d, and also 1, 2, and 4. (You have to be careful here … in base 10 only the prime powers are relevant, because none of the others are relatively prime to 10.) Not coincidentally, those are the same values of n for which the length can possibly be φ(n).

The element −1 can occur in other cases, too, but I don't know any good way to classify those, it is just something that happens sometimes.

Somehow I failed to notice that the converse also holds: if the halves are first complements, then the subgroup contains −1. The proof is really simple, too. Consider the expansion of m/n. If we multiply it by 10^k/2 and add it to itself, the halves shift and combine so that the fractional part is 0.9 = 1. In other words, m/n × (10^k/2 + 1) is an integer. Since n is relatively prime to m, n must go evenly into 10^k/2 + 1. But, that means 10^k/2 + 1 ≡ 0 mod n, which means 10^k/2 ≡ −1, which means the subgroup contains −1. Thus, the halves are complements if and only if the subgroup contains −1!