Pierre de Fermat has a unique reputation in mathematics. The letters and marginalia of this king of mathematical dilettantes has provided mathematicians with powerful tools, but also riddles that took centuries to solve and also outright wrong results. And he's remembered 400 years later.
Modern mathematicians like to render Fermat's theorem as
- ap ≡ a (mod p)
but this isn't what he actually propounded back in 1640 in a letter to a colleague, and it obscures the real power of this concept.
What he actually said was that for any number a and any prime p, there is some minimum exponent d such that p divides ad-1 without a remainder, and that d divides p-1. In modern terms of congruence, we can render this as
- ad≡1 (mod p) and also
p≡1 (mod d) (alternatively p-1 ≡ 0 (mod d)). d may equal p-1, but it also might be a smaller divisor of p-1.
Fermat (unsurprisingly) didn't bother to offer a proof; and the theorem isn't entirely robust because you have to add the qualification that p cannot a factor of a. An immediate conclusion is that
- ap-1 ≡ 1 (mod p)
and we can then band-aid over the qualification with the form ap ≡ a (mod p), but this doesn't add any useful information.
The proof took another 100 years (unsurprisingly, it came from Euler). Somewhat later, Euler published a much more general result for all numbers. The shortcomings of Fermat's presentation has caused many mathematicians to speak of Fermat's theorem only as a special case of Euler's theorem.
If you unpack the proof from above, we can demonstrate the theorem by creating a sequence of numbers, starting with 1, and getting each successive term by multiplying the previous term by a, and taking the remainder when divided by p. It's more instructive to use the remainders with the smallest absolute value.
- Powers of 2, mod 23:
- 1, 2, 4, 8, 16≡-7, +9, -5, -10, +3, +6, -11, +1.
The remainder 1 showed up on the 12th term, which corresponds 211, so 23 must be a factor of 211-1=2047.
- Powers of 2, mod 89:
- 1, 2, 4, 8, 16, 32, -25, +39, -11, -22, -44, +1. 2047=23*89.
- Powers of 2, mod 13:
- 1, 2, 4, -5, +3, +6, -1, -2, -4, +5, -3, -6, +1. 212-1=4095=13*315.
- Powers of 5, mod 23:
- 1, +5, +2, +10, +4, -3, +8, -6, +7, -11, +9, -1, -5, -2, -10, -4, +3, -8, +6, -7, +11, -9, 1.
522-1=2384185791015624=23*103660251783288.
One of the first and most interesting results of Fermat's Little Theorem concerns prime factors of "difficult" Mersenne numbers. A Mersenne number Md=2d-1 can be prime only if d is prime, but it might be composite even if d is prime (like M11). But from Fermat's Little Theorem, if a prime p divides 2d-1, d must divide p-1. But since p-1 is even, d must also divide (p-1)/2. So p must be of the form 2*a*d+1, (where a=[p-1]/[2*d] usually has to be found by trial and error). This shows in our results for M11: 23=2*11+1 and 89=8*11+1.