# LUCAS WILLEMS

A 21 year-old student passionate about maths and programming

# Fermat's little theorem

## Article

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.

Summary

## 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 !