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

  1. É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
  2. É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 ✓.
  3. Étape 3 : On applique, avec p = 11 donc p - 1 = 10 :

    2¹⁰ ≡ 1 (mod 11)

  4. Étape 4 : Vérification directe, possible ici car les nombres restent petits :

    2¹⁰ = 1024 = 11 × 93 + 1 ⟹ 2¹⁰ ≡ 1 (mod 11) ✓

  5. É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.