Fermat's little theorem

Often known as Fermat's theorem, which runs the risk of confusing it with Wiles' theorem. This little fact from number theory was proved by Fermat.

Theorem. Let p be a prime number, and let a be any integer. Then a^p = a (modulo p).

Like the similar Wilson's theorem, the proof of Fermat's little theorem is not too difficult, but a bit hard to grasp at first. The proof originally on the linked node used algebra, and was very different from the proof below, which uses combinatorics. It's based on multiplying the fact that the integers modulo p are a (finite) field. Unfortunately there's an editorial decision to avoid proofs on separate nodes from their theorems. As I believe the proof doesn't belong here (it has nothing to do with how the theorem is applied, which is the usual motive for linking over here), I cannot paste it below. You should be able to reconstruct the proof from the description above; if desperate, /msg me and I'll answer privately.

As an example, take p=5 and a=4. Then 4⁵ = 1024 is clearly 4 modulo 5 (it ends with a 4 or 9 digit).

Fermat theorem:  (a.k.a. "Little Fermat Theorem")
[ i ] If p is a prime and a is an integer, then a ^p ≡ a mod p.  [ ii ] If p is a prime, a is an integer, and k is a positive integer, then a ^pk ≡ a mod p.

Proof: (LEIBNIZ)
     Induction on nonnegative a.

basis step: a = 0.
        0 ^p ≡ 0 mod p.

Induction step:
(1)   (a + 1) ^p ≡ a ^p + 1 ^p mod p
(2)   (a + 1) ^p ≡ a + 1 mod p

(1) holds because the binomial coefficient for each term in the binomial expansion of (x + y) ^p,  p choose r, for 0 < r < p is divisible by p.*  Hence the first and last terms of the expansion remains.  In equation (2), a ^p is congruent to a by the induction hypothesis.

For negative a and odd p, The negative sign factors out and cancels each other.  For negative a and p = 2, the theorem holds because an even squared is always even, and an odd squared is always odd.

[ ii ] is easily proven by induction on k.

QED

---

* p is a divisor of (p choose r) may need a little more explanation:

   (p choose r) = p ! / ( r ! ( p - r ) ! )
   (p choose r) = p ( p - 1 )...( p - r + 1 ) / r !
r! (p choose r) = p ( p - 1)...( p - r + 1 )

p divides the right side, so p must also divide the left side.  Since p's factors are p and 1, and r is less than p, p does not divide r factorial, and so by Euclid's First Theorem, p divides (p choose r).

hooray!

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¹¹, so 23 must be a factor of 2¹¹-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¹²-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²²-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₁₁). 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₁₁: 23=2*11+1 and 89=8*11+1.