Why 1/7 repeats after six digits and 1/13 after six too
Tonight's idea
Divide 1 by 7 by long division. At each step you hold a remainder \(r\). You bring down a 0 to make \(10r\), divide by 7, write the digit, and keep the new remainder. Starting from 1, the remainders run 1, 3, 2, 6, 4, 5 and then 1 again. From there everything repeats: \(\tfrac17 = 0.142857\,142857\dots\)
Each step multiplies the remainder by 10 and reduces mod 7 (keeps the remainder on division by 7). So the remainder after \(k\) steps is \(10^k \bmod 7\).
For a prime \(p\) other than 2 and 5, the period of \(\tfrac1p\) is the smallest \(k \ge 1\) with \(10^k \equiv 1 \pmod p\).
The first remainder to repeat is the starting 1, because 10 has an inverse mod \(p\), so each remainder has only one possible predecessor.
Why the period divides \(p - 1\). The remainder is 1 at steps \(k, 2k, 3k, \dots\) and at no step in between. Fermat's little theorem says \(10^{p-1} \equiv 1 \pmod p\), so step \(p - 1\) is one of those returns. Hence \(p - 1\) is a multiple of \(k\).
Watch one: \(\tfrac{1}{13}\)
The remainders are 1, 10, 9, 12, 3, 4, then 1 again. The digits are 0, 7, 6, 9, 2, 3, so \(\tfrac{1}{13} = 0.076923\,076923\dots\) The period is 6. It divides \(13 - 1 = 12\), as it must, but it is not 12. Here is the period for each prime up to 50:
| \(p\) | 3 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| period | 1 | 6 | 2 | 6 | 16 | 18 | 22 | 28 | 15 | 3 | 5 | 21 | 46 |
Bold marks the primes where the period is the full \(p - 1\). No rule is known that picks them out. In 1927 Emil Artin conjectured that they go on for ever and make up about 37% of all primes. Computer counts agree. Nobody has proved even that there are infinitely many.
Your turn
- Do the long division for \(\tfrac{1}{11}\) and for \(\tfrac{1}{37}\). List the remainders and the digits, and give each period. Check that each divides \(p - 1\).
- For \(p = 17\) the period divides 16. Work out \(10^2\), \(10^4\) and \(10^8\) mod 17 by squaring each answer. Explain why this proves the period is 16.
- A prime has period 5 only if it divides \(10^5 - 1 = 99999 = 3^2 \times 41 \times 271\). Which primes have period exactly 5? Which have period exactly 3?
- \(142857 \times 2 = 285714\) and \(142857 \times 3 = 428571\): the same digits in the same cyclic order. Use the remainder cycle to explain why. Then \(\tfrac{2}{13} = 0.153846\dots\) is not a rotation of 076923. Why not, and how many different cycles do the fractions \(\tfrac{1}{13}, \dots, \tfrac{12}{13}\) need?
Stretch: halves that add to nines
\(142 + 857 = 999\) and \(076 + 923 = 999\). Suppose the period of \(\tfrac1p\) is even, \(2h\). Show that \(10^h \equiv -1 \pmod p\), so the remainder after \(h\) steps is \(p - 1\). Why does that make the two halves add to all nines?
Answers
- \(\tfrac{1}{11}\): remainders 1, 10, then 1; digits 0, 9; \(0.0909\dots\), period 2, and 2 divides 10. \(\tfrac{1}{37}\): remainders 1, 10, 26, then 1; digits 0, 2, 7; \(0.027027\dots\), period 3, and 3 divides 36.
- \(10^2 = 100 \equiv 15\). \(10^4 \equiv 15^2 = 225 \equiv 4\). \(10^8 \equiv 4^2 = 16\). The period is 1, 2, 4, 8 or 16. Each of 1, 2, 4, 8 divides 8, so any of those would make \(10^8 \equiv 1\). It is 16, not 1. So the period is 16.
- Period 5: 41 and 271. (3 also divides 99999, but \(10 \equiv 1 \pmod 3\), so its period is 1.) Period 3: \(p\) divides \(999 = 3^3 \times 37\), so only 37.
- The decimal for \(\tfrac k7\) is the same long division started at remainder \(k\). The cycle 1, 3, 2, 6, 4, 5 contains every possible remainder, so each \(\tfrac k7\) joins the same cycle part-way round and gives the same digits, rotated. For 13 the cycle from 1 holds only 1, 10, 9, 12, 3, 4. The remainder 2 is not there, so \(\tfrac{2}{13}\) runs a second cycle: 2, 7, 5, 11, 6, 8, with digits 153846. Twelve remainders in cycles of six: two cycles.
Stretch. \(10^{2h} \equiv 1\), so \(p\) divides \((10^h - 1)(10^h + 1)\). A prime dividing a product divides one of the factors. It cannot divide \(10^h - 1\), or the period would be at most \(h\). So \(10^h \equiv -1\), and the remainder after \(h\) steps is \(p - 1\). From there the division is that of \(\tfrac{p-1}{p} = 1 - \tfrac1p = 0.999\dots - \tfrac1p\). So each digit in the second half is 9 minus the matching digit in the first half, and the halves add to \(99\dots9\).