Petit théorème de Fermat

Énoncé

Calculer 2^{10} 11 en utilisant le petit théorème de Fermat.

Indice : Comme 11 est premier et 11 2, on a 2^{10} 1 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^{\,p-1} 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^{10} 1 11

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

   2^{10} = 1024 = 11 93 + 1 2^{10} 1 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^{1000} = (2^{10})^{100} 1, et cela sans jamais calculer 2^{1000}. C'est l'objet du 37012. Les DEUX hypothèses comptent : Si p n'est pas premier, c'est faux : 2^{8} = 256 4 9, et non 1. Et si p divise a, c'est faux aussi : 3^{2} = 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^{10} qui vaut 1, pas 2^{11}. 2^{11} = 2^{10} 2 2 : décaler l'exposant d'un cran change complètement le résultat.