Proofs of Fermat's Little Theorem - Proof Using The Binomial Theorem

Proof Using The Binomial Theorem

This proof uses induction to prove the theorem for all integers a ≥ 0.

The base step, that 0 p ≡ 0 (mod p), is true for modular arithmetic because it is true for integers. Next, we must show that if the theorem is true for a = k, then it is also true for a = k+1. For this inductive step, we need the following lemma.

Lemma. For any prime p,

An alternative way of viewing this lemma is that it states that

for any x and y in the finite field GF(p).

Postponing the proof of the lemma for now, we proceed with the induction.

Proof. Assume kp ≡ k (mod p), and consider (k+1)p. By the lemma we have

Using the induction hypothesis, we have that kp ≡ k (mod p); and, trivially, 1p = 1. Thus

which is the statement of the theorem for a = k+1. ∎

In order to prove the lemma, we must introduce the binomial theorem, which states that for any positive integer n,

where the coefficients are the binomial coefficients,

described in terms of the factorial function, n! = 1×2×3×⋯×n.

Proof of lemma. The binomial coefficients are all integers and when 0 < i < p, neither of the terms in the denominator includes a factor of p, leaving the coefficient itself to possess a prime factor of p which must exist in the numerator, implying that

Modulo p, this eliminates all but the first and last terms of the sum on the left-hand side of the binomial theorem for prime p. ∎

The primality of p is essential to the lemma; otherwise, we have examples like

which is not divisible by 4.