This article collects together a variety of proofs of Fermat's little theorem, which states that
for every prime number p and every integer a (see modular arithmetic).
Some of the proofs of Fermat's little theorem given below depend on two simplifications.
The first is that we may assume that a is in the range 0 ≤ a ≤ p − 1. This is a simple consequence of the laws of modular arithmetic; we are simply saying that we may first reduce a modulo p.
Secondly, it suffices to prove that
for a in the range 1 ≤ a ≤ p − 1. Indeed, if (X) holds for such a, then we can simply multiply both sides by a to obtain the original form of the theorem,
and if a happens to be zero, the original equation in its original form is obviously true anyway.
Proof by counting necklaces
This is perhaps the simplest known proof, requiring the least mathematical background. It is an attractive example of a combinatorial proof (a proof that involves counting a collection of objects in two different ways).
Full article ▸