Petit théorème de Fermat
Énoncé
Calculer 2¹⁰ mod 11 en utilisant le petit théorème de Fermat.
Indice : Comme 11 est premier et 11 ∤ 2, on a 2¹⁰ ≡ 1 (mod 11).
Correction
- Étape 1 : Le petit théorème de Fermat donne directement des puissances congrues à 1, ce qui permet ensuite de réduire n'importe quel exposant.
Petit théorème de Fermat :
Si p est premier et si p ne divise pas a :
a ᵖ⁻¹ ≡ 1 p
- Étape 2 : On vérifie les deux hypothèses, car le théorème est faux sans elles : 11 est premier ✓, et 11 ne divise pas 2 ✓.
- Étape 3 : On applique, avec p = 11 donc p - 1 = 10 :
2¹⁰ ≡ 1 (mod 11)
- Étape 4 : Vérification directe, possible ici car les nombres restent petits :
2¹⁰ = 1024 = 11 × 93 + 1 ⟹ 2¹⁰ ≡ 1 (mod 11) ✓
- Étape 5 : L'intérêt n'est pas ce calcul-ci — 1024 se divise à la main — mais ce qu'il permet ensuite : 2¹⁰⁰⁰ = (2¹⁰)¹⁰⁰ ≡ 1, et cela sans jamais calculer 2¹⁰⁰⁰. C'est l'objet du 37012.
Les DEUX hypothèses comptent :
Si p n'est pas premier, c'est faux : 2⁸ = 256 ≡ 4 9, et non 1.
Et si p divise a, c'est faux aussi : 3² = 9 ≡ 0 3. Vérifier les hypothèses AVANT d'appliquer n'est pas une formalité.
L'exposant est p-1, pas p :
Modulo 11, c'est 2¹⁰ qui vaut 1, pas 2¹¹.
2¹¹ = 2¹⁰ × 2 ≡ 2 : décaler l'exposant d'un cran change complètement le résultat.