The original question was: How come the length of the repetend for some fractions (e.g. having a prime number p as a denominator) is equal to p-1?
Physicist: The question is about the fact that if you type a fraction into a calculator, the decimal that comes out repeats. But it repeats in a very particular way. For example,
7 is a prime number and (you can check this) all fractions with a denominator of 7 repeat every 7-1=6 digits (even if it does so trivially with “000000”). The trick to understanding why this happens in general is to look really hard at how division works. That is to say: just do long division and see what happens.
When we say that , what we mean is . With that in mind, here’s why .
and so on forever. You’ll notice that the same thing is done to the numerator over and over: multiply by 10, divide by 7, the quotient is the digit in the decimal and the remainder gets carried to the next step, multiply by 10, …. The remainder that gets carried from one step to the next is just .
Quick aside: If you’re not familiar with modular arithmetic, there’s an old post here that has lots of examples (and a shallower learning curve). The bracket notation I’m using here isn’t standard, just better. “[4]3” should be read “4 mod 3”. And because the remainder of 4 divided by 3 and the remainder of 1 divided by 3 are both 1, we can say “[4]3=[1]3“.
These aren’t the numbers that end up in the decimal expansion, they’re the remainder left over when you stop calculating the decimal expansion at any point. What’s important about these numbers is that they each determine the next number in the decimal expansion, and they repeat every 6.
After this it repeats because, for example, . If you want to change the numerator to, say, 4, then very little changes:
So the important bit to look at is the remainder after each step. More generally, the question of why a decimal expansion repeats can now be seen as the question of why repeats every P-1, when P is prime. For example, for we’d be looking at and for we’d be looking at . The “10” comes from the fact that we use a base 10 number system, but that’s not written in stone either (much love to my base 20 Mayan brothers and sisters. Biix a beele’ex, y’all?).
It turns out that when the number in the denominator, M, is coprime to 10 (has no factors of 2 or 5), then the numbers generated by successive powers of ten (mod M) are always also coprime to M. In the examples above M=7 and the powers of 10 generated {1,2,3,4,5,6} (in a scrambled order). The number of numbers less than M that are coprime to M (have no factors in common with M) is denoted by ϕ(M), the “Euler phi of M”. For example, ϕ(9)=6, since {1,2,4,5,7,8} are all coprime to 9. For a prime number, P, every number less than that number is coprime to it, so ϕ(P)=P-1.
When you find the decimal expansion of a fraction, you’re calculating successive powers of ten and taking the mod. As long as 10 is coprime to the denominator, this generates numbers that are also coprime to the denominator. If the denominator is prime, there are P-1 of these. More generally, if the denominator is M, there are ϕ(M) of them. For example, , which repeats every 12 because ϕ(21)=12. It also repeats every 6, but that doesn’t change the “every 12” thing.
Why the powers of ten must either hit every one of the ϕ(M) coprime numbers, or some fraction of ϕ(M) (, or , or …), thus forcing the decimal to repeat every ϕ(M) will be in the answer gravy below.
Answer Gravy: Here’s where the number theory steps in. The best way to describe, in extreme generalization, what’s going on is to use “groups“. A group is a set of things and an operation, with four properties: closure, inverses, identity, and associativity.
In this case the set of numbers we’re looking at are the numbers coprime to M, mod M. If M=7, then our group is {1,2,3,4,5,6} with multiplication as the operator. This group is denoted ““.
The numbers coprime to M are “closed” under multiplication, which means that if and , then . This is because if you multiply two numbers with no factors in common with M, then you’ll get a new number with no factors in common with M. For example, . No 7’s in sight (other than the mod, which is 7).
The numbers coprime to M have inverses. This is a consequence of Bézout’s lemma (proof in the link), which says that if a and M are coprime, then there are integers x and y such that xa+yM=1, with x coprime to M and y coprime to a. Writing that using modular math, if a and M are coprime, then there exists an x such that . For example, , , , and . Here we’d write , which means “the inverse of 3 is 5”.
The numbers coprime to M have an identity element. The identity element is the thing that doesn’t change any of the other elements. In this case the identity is 1, because in general. 1 is coprime to everything (it has no factors), so 1 is always in regardless of what M is.
Finally, the numbers coprime to M are associative, which means that (ab)c=a(bc). This is because multiplication is associative. No biggy.
So , the set of numbers (mod M) coprime to M, form a group under multiplication. Exciting stuff.
But what we’re really interested in are “cyclic subgroups”. “Cyclic groups” are generated by the same number raised to higher and higher powers. For example in mod 7, {31,32,33,34,35,36}={3,2,6,4,5,1} is a cyclic group. In fact, this is . On the other hand, {21,22,23}={2,4,1} is a cyclic subgroup of . A subgroup has all of the properties of a group itself (closure, inverses, identity, and associativity), but it’s a subset of a larger group.
In general, {a1,a2,…,ar} is always a group, and often is a subgroup. The “r” there is called the “order of the group”, and it is the smallest number such that .
Cyclic groups are closed because .
Cyclic groups contain the identity. There are only a finite number of elements in the full group, , so eventually different powers of a will be the same. Therefore,
That is to say, if you get the same value for different powers, then the difference between those powers is the identity. For example, and it’s no coincidence that .
Cyclic groups contain inverses. There is an r such that . It follows that . So, .
And cyclic subgroups have associativity. Yet again: no biggy, that’s just how multiplication works.
It turns out that the number of elements in a subgroup always divides the number of elements in the group as a whole. For example, ={1,2,3,4,5,6} is a group with 6 elements, and the cyclic subgroup generated by 2, {1,2,4}, has 3 elements. But check it: 3 divides 6. This is Lagrange’s Theorem. It comes about because cosets (which you get by multiplying every element in a subgroup by the same number) are always the same size and are always distinct. For example (again in mod 7),
The cosets here are {1,2,4} and {3,5,6}. They’re the same size, they’re distinct, and together they hit every element in . The cosets of any given subgroup are always the same size as the subgroup, always distinct (no shared elements), and always hit every element of the larger group. This means that if the subgroup has S elements, there are C cosets, and the group as a whole has G elements, then SD=G. Therefore, in general, the number of elements in a subgroup divides the number of elements in a whole group.
To sum up:
In order to calculate a decimal expansion (in base 10) you need to raise 10 to higher and higher powers and divide by the denominator, M. The quotient is the next digit in the decimal and the remainder is what’s carried on to the next step. The remainder is what the “mod” operation yields. This leads us to consider the group of which is the multiplication mod M group of numbers coprime to M (the not-coprime-case will be considered in a damn minute). has exactly ϕ(M) elements. The powers of 10 form a “cyclic subgroup”. The number of numbers in this cyclic subgroup must divide ϕ(M), by Lagrange’s theorem.
If P is prime, then ϕ(P)=P-1, and therefore if the denominator is prime the length of the cycle of digits in the decimal expansion (which is dictated by the cyclic subgroup generated by 10) must divide P-1. That is, the decimal repeats every P-1, but it might also repeat every or or whatever. You can also calculate ϕ(M) for M not prime, and the same idea holds.
Deep Gravy:
Finally, if the denominator is not coprime to 10 (e.g., 3/5, 1/2, 1/14, 71/15, etc.), then things get a little screwed up. If the denominator is nothing but factors of 10, then the decimal is always finite. For example, .
In general, if the denominator has powers of 2 or 5, then the resulting decimal will be a little messy for the first few digits (equal to the higher of the two powers, for example 8=23) and after that will follow the rules for the part of the denominator coprime to 10. For example, . So, we can expect that after two digits the decimal expansion will settle into a nice six-digit repetend (because ϕ(7)=6).
Fortunately, the system works:
This can be understood by looking at the powers of ten for each of the factors of the denominator independently. If A and B are coprime, then . This is an isomorphism that works because of the Chinese Remainder Theorem. So, a question about the powers of 10 mod 28 can be explored in terms of the powers of 10 mod 4 and mod 7.
Once the powers of 10 are a multiple of all of the of 2’s and 5’s in the denominator, they basically disappear and only the coprime component is important.
Numbers are a whole thing. If you can believe it, this was supposed to be a short post.