Sciences · Mathématiques
Le petit théorème de Fermat
Le petit théorème de Fermat affirme que si p est un nombre premier, alors aᵖ − a est divisible par p pour tout entier a. Si a n’est pas multiple de p, cela s’écrit a^(p−1) ≡ 1 (mod p).
Mis à jour le 4 min de lecture
Pierre de Fermat, magistrat toulousain et mathématicien amateur de génie, énonce ce résultat dans une lettre à Frénicle de Bessy en 1640, sans démonstration. La première preuve publiée est due à Leonhard Euler en 1736. À ne pas confondre avec le grand théorème de Fermat, démontré seulement en 1994 : le « petit » théorème est un outil de base de l'arithmétique modulaire, utilisé chaque jour par les systèmes de chiffrement.
Vérifier sur des exemples
| p | a | Calcul | Reste modulo p |
|---|---|---|---|
| 5 | 2 | 2⁴ = 16 = 3 × 5 + 1 | 1 |
| 7 | 3 | 3⁶ = 729 = 104 × 7 + 1 | 1 |
| 3 | 4 | 4² = 16 = 5 × 3 + 1 | 1 |
| 5 | 10 | 10⁵ − 10 = 99 990 = 5 × 19 998 | divisible (forme 1) |
À quoi sert-il ?
Calculer des restes de grandes puissances
Calculer un inverse modulaire
Si p ne divise pas a, a × a^(p−2) ≡ 1 (mod p) : l’inverse de a modulo p est a^(p−2). Exemple : l’inverse de 3 modulo 7 est 3⁵ = 243 ≡ 5, et en effet 3 × 5 = 15 ≡ 1 (mod 7).
Tester si un nombre est premier
Si, pour un nombre n et un entier a premier avec n, on trouve a^(n−1) ≢ 1 (mod n), alors n n’est pas premier. C’est le test de Fermat, très rapide sur ordinateur.
La réciproque est fausse : certains nombres composés vérifient la congruence. 341 = 11 × 31 satisfait 2³⁴⁰ ≡ 1 (mod 341) : c’est un pseudo-premier en base 2. Pire, les nombres de Carmichael (561 = 3 × 11 × 17 est le plus petit) la vérifient pour toutes les bases premières avec eux. Les tests modernes (Miller-Rabin) corrigent ce défaut.
Une démonstration
Soit p premier et a non divisible par p. On considère les p − 1 nombres a, 2a, 3a, …, (p − 1)a.
- Aucun n’est divisible par p (p ne divise ni a ni k < p).
- Leurs restes modulo p sont tous différents : si
ia ≡ ja, alors p divise(i − j)a, donc p divisei − j, impossible pour deux nombres distincts entre 1 et p − 1. - Ces restes sont donc exactement
1, 2, …, p − 1, dans un autre ordre. - En multipliant tout :
a^(p−1) × (p − 1)! ≡ (p − 1)! (mod p). - Comme
(p − 1)!est premier avec p, on simplifie :a^(p−1) ≡ 1 (mod p).
La simplification de l’étape 5 est justifiée par le théorème de Bézout ou le lemme de Gauss. Voir aussi la factorielle.
Généralisation d’Euler et chiffrement RSA
Euler généralise le théorème à un module n quelconque : si a est premier avec n, alors a^φ(n) ≡ 1 (mod n), où φ(n) (l'indicatrice d’Euler) compte les entiers de 1 à n premiers avec n. Pour p premier, φ(p) = p − 1 et l’on retrouve Fermat.
Le chiffrement RSA (1977) repose sur ce théorème : avec n = p × q (deux grands nombres premiers), on chiffre un message m en c = mᵉ mod n et on le déchiffre en m = cᵈ mod n, où d est choisi pour que e × d ≡ 1 (mod φ(n)). Le théorème d’Euler garantit qu’on retrouve bien le message. Retrouver d sans connaître p et q revient en pratique à factoriser n, ce qui est hors de portée pour des nombres de plusieurs centaines de chiffres (voir le chiffrement HTTPS).
Erreurs fréquentes
- Oublier la condition « p premier » :
2³ = 8 ≡ 0 (mod 4), pas 1. - Appliquer la forme 2 quand p divise a :
5⁴ ≡ 0 (mod 5). - Croire à la réciproque :
a^(n−1) ≡ 1 (mod n)ne prouve pas que n est premier.
Questions fréquentes
Quelle différence entre le petit et le grand théorème de Fermat ?
Le petit théorème porte sur les puissances modulo un nombre premier et se démontre en quelques lignes. Le grand affirme que xⁿ + yⁿ = zⁿ n’a pas de solution entière positive pour n ≥ 3 ; il a fallu attendre Andrew Wiles (1994) pour le prouver.
Comment utiliser le petit théorème de Fermat pour un reste ?
On réduit l’exposant modulo p − 1 : pour aᵏ mod p, on écrit k = (p − 1)q + r, et aᵏ ≡ aʳ (mod p).
Qu’est-ce qu’un nombre de Carmichael ?
Un nombre composé n qui vérifie a^(n−1) ≡ 1 (mod n) pour tout a premier avec n. Le plus petit est 561 ; il en existe une infinité (démontré en 1994).
Fermat a-t-il démontré ce théorème ?
Il affirme en avoir une preuve mais ne la publie pas. Leibniz en rédige une dans des notes non publiées ; la première démonstration publiée est celle d’Euler en 1736.