Page 322:
2^{10} − 1 = 1023 = 11 × 93
3^{10} − 1 = 59048 = 11 × 5368 4^{10} − 1 = 1048575 = 11 × 95325
5^{10} − 1 = 9765624 = 11 × 887784 6^{10} − 1 = 60466175 = 11 × 5496925...
999999 breaks down into prime factors as 3^{3} × 7 × 11 × 13 × 37. So out of the decimals for fractions 1/p, p a prime, only 1/3, 1/7, 1/11, 1/13 and 1/37 can recur with period 6.
9999 = 3^{2} × 11 × 101. So only 1/3, 1/11 and 1/101 recur with period 4.
This question shows the difficulty of finding the factors of even a 7figure number like 9999999. You may find it helpful to use my factorisation applet.
9999999 = 3^{2} × 239 × 4649. So only 1/3, 1/239 and 1/4649 recur with period 7. In fact 1/239 = .0041841 recurring, 1/4649 = .0002151 recurring
Only 1/21649 and 1/513239 recur in groups of 11.
To find 1/5 in binary notation, you could do long division in binary. However, it is easier to use the 'geometric progression' principle. 5 must divide into 2^{4} − 1, by Fermat's theorem, and indeed it does since 5 × 3 = 15. Now using r = 1/16, the formula for geometric progressions gives:
1/15 = 1/16 + 1 /16^{2} + 1/16^{3}... = .0001000100010001...
So 1/5 = 3/15 = .0011001100110011...
A calculator working in binary will therefore not be able to hold 1/5 exactly. For such a calculator, 1/5 is just as awkward as 1/3, which a tenbased calculator cannot store exactly.
Is this to be thought of as a fault or defect of binary arithmetic? Not in any deep sense, but from a practical point of view it is a disadvantage to have inconsistency with tenbased working. My impression is that calculators given as software on computers now store numbers as if they were working in decimal notation. The Power Mac of the 1990s was unusual in working directly in binary.
The deeper point illustrated by all this is Turing's principle that a computer, as a universal machine, can perform calculation in any base you like, just by running the right software. The binary basis of its hardware is not very important.
To see how the calculator is actually storing numbers, try entering 1/3, then mulitplying by 10 repeatedly, subtracting off the 3 at the beginning each time. It will reveal a string of 3's of a finite length, determined by the precision used.
This problem amounts to asking what is the first power of 6 that is congruent to 1, modulo 13. Fermat tells us that 6^{12} has this property. 6^{2} = 10 modulo 13, so it cannot be true that 6^{6} = 1 modulo 13 as this would imply 10^{3} = 1 modulo 13 which is not true.
This also means that 6^{3} is not 1 modulo 13, and
6^{2}, 6^{4} can't be 1 modulo 13 either.
Explicitly, 1/13 in base6 is .024340531215 recurring = 167444795 /(6^{12} − 1).
The argument for base7 is the same.
By an extension of this argument, you can see that in base 9, 1/13 has a recurring period of 3 (actually .062 recurring), in base 5 of length 4 (actually .0143 recurring), and in base 8 of length 4 (actually .0473 recurring).
This is an extension of the idea of a geometric series. Again write r for 1/10. Then we want to show that
1/89 = F_{0} × r + F_{1} × r^{2} + F_{2} × r^{3} + F_{3} × r^{4}...
where F_{0}, F_{1}, F_{2}, F_{3}... are the Fibonacci numbers 0, 1, 1, 2...
Multiply both sides by (1 − r − r^{2}). All the terms cancel, because of the property of the Fibonacci numbers, except for
F_{0} × r +
F_{1} × r^{2} −
F_{0} × r^{2}
and this is just r^{2} = 1/100.
But (1 − r − r^{2}) is just 89/100, so this verifies the equation.
Putting r = 1/10000 instead, we find that 1/9899 = .000102030508132134...
For a more direct approach to Fermat's Little Theorem, take the example of p=7, and look at the 7th row of the Pascal triangle, which is:
1, 7, 21, 35, 35, 21, 7, 1.
It is noticeable that all the entries, apart from the 1's at the ends, are divisible by 7. Is this a fluke? No: there is good reason, which depends on knowing the connection with the factorials.
The 35, for instance, arises as 7!/(3! × 4!), representing the number of ways of choosing 3 things out of 7. The 7! has a factor of 7 in it, but 3! and 4! do not. So the factor of 7 must be present in the number 7!/(3! × 4!), as indeed it is. The same argument applies to any number in the pth row, when p is a prime. (It does not apply if p is not a prime).
The numbers in the pth row of the Pascal triangle sum to 2^{p}. Subtracting the two 1's at the ends, the number 2^{p} − 2 must be divisible by p, and this is Fermat's Little Theorem.
