L’arithmétique modulaire s’intéresse aux restes de la division euclidienne. On dit que deux entiers $a$ et $b$ sont congrus modulo n, et on note $a \equiv b \pmod{n}$, si $a$ et $b$ ont le même reste dans la division par $n$. Cela équivaut à dire que leur différence $a-b$ est un multiple de $n$.
Par exemple, $17 \equiv 2 \pmod{5}$ car $17-2=15$, qui est un multiple de 5.
Le théorème se présente sous deux formes équivalentes :
- Version 1 : Si $p$ est un nombre premier, alors pour tout entier $a$, le nombre $a^p – a$ est divisible par $p$. En notation modulaire : $$ a^p \equiv a \pmod{p} $$
- Version 2 : Si $p$ est un nombre premier et $a$ est un entier non divisible par $p$, alors le nombre $a^{p-1} – 1$ est divisible par $p$. En notation modulaire : $$ a^{p-1} \equiv 1 \pmod{p} $$
Démonstration (par récurrence sur a)
Nous allons démontrer la première version, $a^p \equiv a \pmod{p}$, par récurrence sur l’entier $a \ge 0$.
Étape 1 : Cas de base (a=0)
Pour $a=0$, la proposition est $0^p \equiv 0 \pmod{p}$, ce qui est trivialement vrai.
Étape 2 : Hérédité
Supposons que la propriété est vraie pour un certain entier $a \ge 0$. C’est notre hypothèse de récurrence : $$ a^p \equiv a \pmod{p} $$ Nous devons montrer que la propriété est également vraie pour $a+1$, c’est-à-dire $(a+1)^p \equiv a+1 \pmod{p}$.
Développons $(a+1)^p$ en utilisant la formule du binôme de Newton : $$ (a+1)^p = \sum_{k=0}^p \binom{p}{k} a^k 1^{p-k} = \binom{p}{0}a^0 + \binom{p}{1}a^1 + \dots + \binom{p}{p-1}a^{p-1} + \binom{p}{p}a^p $$ $$ (a+1)^p = 1 + \sum_{k=1}^{p-1} \binom{p}{k} a^k + a^p $$ Pour avancer, nous avons besoin d’un lemme sur les coefficients binomiaux.
Si $p$ est un nombre premier, alors pour tout entier $k$ tel que $1 \le k \le p-1$, le coefficient binomial $\binom{p}{k}$ est un multiple de $p$.
Preuve du lemme : On a $\binom{p}{k} = \frac{p!}{k!(p-k)!}$. Comme $p$ est premier et $k < p$, le nombre premier $p$ apparaît comme facteur au numérateur. Cependant, tous les facteurs de $k!$ et $(p-k)!$ sont strictement inférieurs à $p$, donc $p$ ne peut pas être simplifié. Par conséquent, $p$ doit diviser $\binom{p}{k}$.
En revenant à notre développement, le lemme nous dit que tous les termes de la somme $\sum_{k=1}^{p-1} \binom{p}{k} a^k$ sont des multiples de $p$. Leur somme est donc aussi un multiple de $p$. En termes de congruence, cela signifie : $$ \sum_{k=1}^{p-1} \binom{p}{k} a^k \equiv 0 \pmod{p} $$ L’équation du binôme devient donc : $$ (a+1)^p \equiv 1 + 0 + a^p \pmod{p} $$ En utilisant notre hypothèse de récurrence ($a^p \equiv a \pmod{p}$), on obtient : $$ (a+1)^p \equiv 1 + a \pmod{p} $$ Ceci est exactement la propriété que nous voulions démontrer pour $a+1$.
Étape 3 : Conclusion
Par le principe de récurrence, la propriété $a^p \equiv a \pmod{p}$ est vraie pour tous les entiers $a \ge 0$. On peut facilement l’étendre aux entiers négatifs.
Implications et Utilisation
- Tests de Primalité : Le théorème fournit un test pour savoir si un nombre n’est pas premier. Si on trouve un entier $a$ tel que $a^{n-1} \not\equiv 1 \pmod{n}$, alors on est certain que $n$ n’est pas premier. (Attention, la réciproque n’est pas toujours vraie).
- Cryptographie (RSA) : Le petit théorème de Fermat est le pilier mathématique qui assure le fonctionnement de l’algorithme de chiffrement RSA. Il garantit que le déchiffrement d’un message chiffré redonne bien le message original. L’algorithme repose sur une généralisation (le théorème d’Euler) qui s’applique aux nombres non premiers.