*Fermat's Little Theorem* asserts that if p is a prime and a an integer then p divides a^p - a , or, which is equivalent, that p dvides a^{p-1} - a , provided p does not divide a , i.e. when (p, a) = 1.

Euler was the first to publish a proof. He also generalized the theorem after introducing his \phi function. The first of his proofs depends on the following

### Lemma

For any integers a, b and any prime p ,

In other words

### Proof:

The proof makes use of a property of binomial coefficients. The binomial coefficient

is an integer for 0 \lt k \lt p since it counts the number of subsets of size k of a set of p elements. The factor p occurs in the numerator but not in the denominator. It follows by the unique factorization that

for 0 \lt k \lt p. The lemma now follows from the binomial theorem.

Now return to the theorem. The case a \lt 0 follows from that of a \gt 0. So we tackle the latter. For a fixed prime p we run induction on a.

If a = 0 then, of course, p|a.

Assume the theorem holds for a = k and let now a = k+1. By the lemma,

In other words,

By the induction hypothesis, p|k^p-k so that also

which serves the induction goal.

### A Geometrical proof

A visualizable proof of Fermat's Little Theorem is here.

### References

- J. R. Goldman,
*The Queen of Mathematics*, A K Peters, 1998