It is explained how, for a given natural number, the period length of the decimal fraction of the reciprocal of that number can be determined without actually performing the division. The article begins with examples in the decimal number system, but the theory is then displayed for arbitrary bases of number systems. The reader should be able to apply the statements in the beginning to other bases as well.
First of all, we observe that factors 2 and 5 in the denominator change neither the period length nor the sequence of digits in the period, their influence can always be separated into an extra summand, e.g.: 1/12 = 1/3 – 1/4 or 1/70 = 5/7 – 7/10, and the decimal expansions of 1/4 and 7/10 terminate. The effect is that this extra summand garbles the first few digits so that the period does not start at the decimal point. Another way to handle this case is to multiply the fraction with the least power of 10 that makes the factors 2 and 5 in the denominator disappear: 100/12 = 25/3 = 8 + 1/3, then to look at the decimal fraction, and to shift the decimal point to the left again to compensate for the power of 10 introduced in the first step.
Now, we are only interested in the cases where the denominator has no factor 2 or 5, i.e. ends in a digit 1, 3, 7, or 9. It is easy to see that in this case the period starts right at the decimal point:
0.294347 294347 ... = 294347 / 999999 0.142857 142857 ... = 142857 / 999999 = 1 / 7
Multiplying with a constant leaves the period intact. If this constant happens to be a factor of the denominator, the period may be shortened, but even then the decimal fraction is still periodic with the previous period length:
0.002457 002457 ... = 2457 / 999999 = 1 / 407 0.149877 149877 ... = 149877 / 999999 = 61 / 407 0.135135 135135 ... = 135135 / 999999 = 55 / 407 = 5 / 37 0.135 135 135 135 ... = 135 / 999 = 5 / 37
This way to look at decimal fractions gives us the clue to period lengths:
For denominator q, the period length is the smallest k such that q divides 10k–1. E.g. for 41, the period length is 5 because 41 divides 99999.
From this we get some useful consequences:
For any denominator q = p1a1 ×
p2a2 × . . . (prime factor decomposition),
the period length is a factor of
φ(q) = (p1–1)p1a1–1 × (p2–1)p2a2–1 × . . .
(number of those integers smaller than q that have no common
factor with q). As a special case:
For a prime denominator q, the period length is a factor of q–1.
The period length of the least common multiple of q1 and q2 is the least common multiple of the two period lengths.
Examples:
9997 = 13 × 769, hence the period length of 9997 is a factor of 12 × 768 = 9216. Indeed, it is 192, which is 9216/48.
We could have found that also the other way round:
The period length of 13 is 6, that of 769 is 192, so the period length of
9997 is the LCM of 6 and 192, namely 192.
The proofs of the three statements are omitted here. The first (and hence also the second) is an immediate consequence of Fermat's Little Theorem, and the third is easy to see if one computes the greatest common divisor of two different 10k–1 by Euclid's algorithm.
Now we are nearly done:
For a given q, divide it into powers of primes. For each prime power, determine the period length, then take the LCM of all these.
For a prime power pk, determine first two things:
The period length L of p.
The highest power pj such that the period length of pj is also L.
Then the period length of pk is pk–j × L if k>j, otherwise L. If the denominator is a factor of of b–1 where b ist the base of the number system, this rule may not be true for the first step: in this case let L be the period length of p2 instead; the reader may try for himself the case p=2 in base b=3.
This follows relatively easy from the above observations if j>1. In case j=1 (the normal case), it is also true, but more tedious to prove.
Some examples: The period length of 3 (in base 10) is 1, of 9 as well, of 27 not. Hence 27 has period length 3, 81 has 9 and so on. Here the case j>1 is somewhat "artificial" as the square of 3 is a factor of b–1=9. A more "natural" case would be one where p and b–1 have no common divisor, e.g. p=7 in base 18: not only 7 but 73 divides 183–1, so that the period length of 73 in that base is the same as that of 7, namely 3. For base 10, i.e. for decimal numbers, the smallest such "natural" examples are p=487 and p=56598313 where p2 has the same period length (p–1 in both cases) as p itself. Interesting are of course only those cases where the smallest bk–1 that is a multiple of p is also a multiple of a higher power of p. More examples for other bases are: 10932 is a factor of 2364–1, 112 is a factor of 35–1, 52 is a factor of 74–1, 134 is a factor of 2394–1, 54 is a factor of 4434–1, and 56 is a factor of 10684–1.
Remains the case of a prime p. The only candidates are the factors of p–1. In other words, we have to find K such that the period length is (p–1)/K. In which cases K is even can be determined by quadratic residues: K is even if and only if the base b of the number system is a quadratic residue modulo p. For base 10, this is the case if and only if the distance of p to the nearest multiple of 40 is one of 1, 3, 9, or 13. For other K, one would have to look for the solvability of higher-order roots modulo 10. Here are some examples of primes, ordered by K:
| K | Examples of primes p such that the decimal period length of 1/p is (p–1)/K |
|---|---|
| 3 | 103, 127, 139, 331, 349, 421, 457, 463, 607, 661, 673, 691, 739, 829, 967, 1657, 1669, 1699, 1753, 1993 |
| 4 | 53, 173, 277, 317, 397, 769, 773, 797, 809, 853, 1009, 1013, 1093, 1493, 1613, 1637, 1693, 1721 |
| 5 | 11, 251, 1061, 1451, 1901, 1931, 2381, 3181, 3491, 3851, 4621, 4861, 5261, 6101, 6491, 6581, 6781 |
| 6 | 79, 547, 643, 751, 907, 997, 1201, 1213, 1237, 1249, 1483, 1489, 1627, 1723, 1747, 1831, 1879, 1987 |
| 7 | 211, 617, 1499, 2087, 2857, 6007, 6469, 7127, 7211, 7589, 9661, 10193, 13259, 13553, 14771, 18047 |
| 8 | 41, 241, 1601, 1609, 2441, 2969, 3041, 3449, 3929, 4001, 4409, 5009, 6089, 6521, 6841, 8161, 8329 |
| 9 | 73, 1423, 1459, 2377, 2503, 3457, 7741, 9433, 10891, 10909, 16057, 17299, 17623 |
| 10 | 281, 521, 1031, 1951, 2281, 2311, 2591, 3671, 5471, 5711, 6791, 7481, 8111, 8681, 8761, 9281 |
| 11 | 353, 3499, 10429, 13619, 15269, 20219, 20593 |
| 12 | 37, 613, 733, 1597, 2677, 3037, 4957, 5197, 5641, 7129, 7333, 7573, 8521, 8677, 11317, 14281 |
| 13 | 2393, 15497, 18149, 18617, 20021, 25819, 26183 |
| 14 | 449, 1289, 3557, 4397, 4999, 5209, 6203, 6637, 7043, 8387, 10613, 11369, 13147, 13399, 14323 |
| 15 | 3061, 4021, 7621, 11491, 14851, 19381, 22651 |
| 16 | 1889, 5521, 8849, 9521, 9649, 12689, 13649, 17681, 17729, 18049 |
| 17 | 137, 9419, 25127, 27541, 51341, 80207, 85103 |
| 18 | 2467, 3187, 4357, 4483, 5689, 7039, 7237, 8317, 9973, 10243, 10711, 10729, 11071, 12763, 13267 |
| 19 | 16189, 23447, 29527, 30971, 37811, 79687, 88807 |
| 20 | 641, 3121, 13921, 23041, 23561, 26681, 29921 |
| 24 | 1321, 6481, 11689, 16729, 19081, 24001, 31849 |
| 25 | 101, 15101, 17851, 19501, 39251, 46901, 59651 |
| 28 | 757, 9689, 12853, 14533, 15877, 20693, 55889 |
| 30 | 1231, 11311, 14551, 21991, 23911, 27751, 28111 |
| 33 | 859, 40063, 42703, 63097, 167113, 173713, 181303 |
| 34 | 239, 11969, 12071, 13907, 26759, 34511, 58889 |
| 44 | 1409, 3169, 20681, 42197, 43517, 68597, 84437 |
| 54 | 271, 21871, 23599, 32401, 36559, 40879, 43201 |
| 92 | 1933, 51613, 150053, 470489, 639493, 1108693, 1651493 |
This list is exhaustive for primes under 2000: if a prime p is under 2000 and does not appear in this list, its period length is either p–1 (if K odd, see above for the criterion) or (p–1)/2. For each of the K, there are no other possible p between the listed ones; the point where each list ends is, however, quite unsystematic (but it will not end before 2000 is reached).
The largest values of K belong to the large prime factors of numbers that consist only of ones ("repunits"), e.g. 265371653, which is a factor of 1111111111111, has a period length of 13 which leads to K=20413204. The largest K known belongs to the largest repunit which is completely factorised; this is currently the prime number (101031–1)/9 with a period length of 1031 and hence K near 1.0777×101027.
How period lengths for prime numbers of moderate size can be determined with modest means (for p<100000 even with a non-programmable pocket calculator), is described in the next section.
Now that we know basic facts about the length of the period of a decimal fraction, we look at an example of how such a period length can actually be computed, even with modest means.
The example is with a prime number, p=523. In this case, it is known that the period length is a factor of p–1. For general (not necessarily prime) n the same method can be employed, but then not with n–1 but with φ(n) which in turn is n–1 if and only if n is prime. In practice, this is not recommended: in order to compute φ(n), one has to decompose n into prime factors, and if one has done that, it is easier to compute the period lengths for the factors of n separately.
The factorisation of p–1 is: 522 = 2 × 3 × 3 × 29
Compute some 10i mod 523, so that as many factors of 522 as possible appear among the i:
| i | 10i mod 523 | equals |
|---|---|---|
| 7 | 107 mod 523 | 240 |
| 14 | 2402 mod 523 | 70 |
| 29 | (702×10) mod 523 | 361 |
| 58 | 3612 mod 523 | 94 |
| 87 | (361×94) mod 523 | 462 |
| 174 | 4622 mod 523 | 60 |
| 261 | (462×60) mod 523 | 1 |
This computation always ends with 1 because ap–1 mod p = 1 for all 0<a<p. If not, then either p is not a prime or you have made a mistake somewhere.
Draw conclusions.
The period length has to be a factor of 261 but none of the numbers in the list. The only factors that remain are 1, 2, 3, 6, 9, 18.
Start over. Same as step 1 but this time have as many of the remaining candidates as possible appear in the list.
(Since 18 is so small, you can take a shortcut: 109 mod 523 is neither 1 nor –1, so there is no need to compute 1018 mod 523.)
No further i with 10i mod 523 are found. Thus the answer is 261.