Petit théorème de Fermat

Théorème
se lit "modulo p".

Preuve
Utilisons la formule du binôme :

.

Or, étant donné un entier , ,

on trouve que . Cela prouve que p divise .

Or, p est premier avec k! puisqu'on a .

Donc, d'après le théorème de Gauss, p divise . En d'autres termes .
Cela implique : .

Théorème
Remarque
Ce théorème a été énoncé en 1640 puis démontré en 1683 par Leibniz et de nouveau démontré par Euler en 1736.

Preuve
Nous allons démontrer ce théorème par récurrence sur l'entier a. Pour cela, fixons un nombre premier p et raisonnons modulo p.

Soit P_a la phrase "".
Pour a = 0, on a bien . P₀ est donc vraie.

Soit a un entier naturel quelconque. Supposons que P_a soit vraie et démontrons P_a+1 :

d'après le théorème précédent.

d'après l'hypothèse de récurrence.

On en déduit que et donc P_a+1 est vraie.

Bilan : P_a est vraie pour tout entier naturel a et p quelconque.

Théorème
Preuve
D'après le théorème précédent, on sait que p divise , donc .

Ne divisant pas a, p est premier avec a. D'après le théorème de Gauss p divise , donc modulo p, ce qu'il fallait démontrer.

Remarque
Le petit théorème de Fermat et son corollaire sont à la source de certaines méthodes de cryptographie, notamment la méthode RSA (initiales des inventeurs : Ronald Rivest, Ali Shamir et Leonard Adleman dans les années 1970) et la méthode de Tahar El Gamal, au milieu des années 1980.