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} - 1 ,  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

p | (a + b)^p - a^p - b^p

In other words

(a + b)^p - a^p - b^p \equiv 0\quad \pmod{p}

Proof:

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

{p \choose k} = \frac{p(p-1)...(p-k+1)}{k!}

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

p|{p \choose k}

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,

(k+1)^p \equiv k^p + 1 \pmod{p}.

In other words,

(k+1)^p - (k+1) \equiv k^p - k \pmod{p}.

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

p|(k+1)^p - (k+1)

which serves the induction goal.

A Geometrical proof

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

References