Fermat's little theorem states that if p is a prime number (such as 2, 3, 5, 7, 11 or 5,273) and a is an integer not divisible by p, then *a p*–1 – 1 is divisible by p. For small values of a and p, the result may not seem spectacular, and the theorem may not look particularly useful. But with sufficiently large values, the calculations quickly become unmanageable, and the theorem can come to our rescue.
There are many proofs of this theorem, some of them highly original. One of the most standard begins with the following list of multiples of a: a, 2a, 3a, 4a… (p – 1) a. Let r1, r2… *rp*–1 be the respective remainders when these numbers are divided by p. None of these remainders is 0, since none of the multiples of a on our list is divisible by p (see the box on Gauss's lemma). Furthermore, all these remainders are distinct. Suppose that rk and rk' are equal, with k ≤ k'. Then k'a – ka, or (k' – k) a, is a multiple of p. The same argument as before shows that p divides k' – k. Since k' – k is a non-negative integer strictly less than p, its only possible value is 0. In other words, k = k'.
These remainders therefore take the values 1, 2, 3… and p – 1, though not necessarily in that order. We need only observe that the product a × 2a × 3a × … × (p – 1) a is congruent to 1 × 2 × 3 × … × (p – 1) modulo p. It follows that *a p*–1 (p – 1)! is congruent to (p – 1)! modulo p. In other words, p divides *a p*–1(p – 1)! – (p – 1)!, but does not divide (p – 1)!. By Gauss's lemma, p does indeed divide *a p*–1 – 1.
-
Enter Euler
--------------------
