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

`a`^{p} ≡ 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 `a`^{d}-1 without a remainder, and that `d` divides `p-1`. In modern terms of congruence, we can render this as

`a`^{d}≡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

`a`^{p-1} ≡ 1 (mod p)

and we can then

band-aid over the qualification with the form

`a`^{p} ≡ 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 2^{11}, so 23 must be a factor of 2^{11}-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.
**2**^{12}-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.

**5**^{22}-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 M_{d}`=2`^{d}-1 can be prime only if `d` is prime, but it might be composite even if `d` is prime (like M_{11}). But from Fermat's Little Theorem, if a prime `p` divides `2`^{d}-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 M_{11}: 23=2*11+1 and 89=8*11+1.