In the year 1640, Pierre de Fermat expresses the following theorem :

If \(p\) is a prime number and \(a\) is some integer, then \(a^p - a\) is divisible by \(p\).

But Fermat didn't leave a proof of his theorem. So, I'm going to show you how to prove it.

Proof

To prove this theorem, let's use induction with this statement :

$$\forall a \in \mathbb{N} \qquad H_a : a^p - a \equiv 0 [p]$$

where \(p\) is a prime number, that leads us to the following reasoning :

Bases :
For \(a = 0\), \(0^p - 0 = 0 \equiv 0 [p]\). So, \(H_0\) holds.

Induction steps:
For \(a+1\) :

$$(a+1)^p - (a+1) = \sum_{k=0}^{p} \binom{p}{k} a^k - (a+1) = \left( \sum_{k=1}^{p-1} \binom{p}{k} a^k \right) + a^p - a$$

As \(\binom{p}{k} = \frac{p!}{k! (p-k)!}\) with \(k \in [[1, p-1]]\), \(k < p\) and \(p-k < p\). So, because \(p\) is prime, \(p\) isn't divisible by the factors of \(k!\) and \((p-k)!\). So, \(\frac{p!}{k! (p-k)!}\), \(\binom{p}{k}\), but also \(\sum_{k=1}^{p-1} \binom{p}{k} a^k\) are divisible by \(p\).

Furthermore, as we assume \(H_a\) holds, \(a^p - a\) is also divisible by \(p\). Therefore, \((a+1)^p - (a+1) \) is divisible by \(p\), which means that \(H_a \Rightarrow H_{a+1}\).

Conclusion :
\(H_a\) holds \(\forall a \in \mathbb{N}\).

We have just proved Fermat's little theorem !