Puissance modulo $p$

Énoncé

Calculer 3^{100} 7.

Indice : Utilise le petit théorème de Fermat pour réduire l'exposant.

Correction

1. Étape 1 : 3^{100} a quarante-huit chiffres : il n'est pas question de le calculer. L'idée est de trouver une puissance qui vaut 1, puis de découper l'exposant par une division euclidienne.
2. Étape 2 : Fermat donne le cycle. 7 est premier et ne divise pas 3, donc :

   3^{6} 1 7

3. Étape 3 : On divise l'exposant par 6, la longueur du cycle :

   100 = 6 16 + 4

4. Étape 4 : On découpe la puissance en conséquence :

   3^{100} = 3^{6 16 + 4} = (3^{6})^{16} 3^{4}

5. Étape 5 : Le premier facteur vaut 1^{16} = 1, donc il ne reste que 3^4 :

   3^{100} 3^4 = 81 7

6. Étape 6 : On réduit une dernière fois :

   81 = 7 11 + 4 3^{100} 4 7

7. Étape 7 : Le RESTE de la division est ce qui compte, pas le quotient : c'est lui qui donne l'exposant résiduel. Le 16 ne sert qu'à disparaître. Ne pas confondre le reste de l'exposant et le résultat : Le reste 4 de la division 100 = 616+4 est un EXPOSANT : il faut encore calculer 3^4 = 81, puis réduire modulo 7. Répondre « 3^{100} 4 car le reste est 4 » tombe juste ici par pure coïncidence — 81 4 aussi. Avec 3^{101}, le reste serait 5 et la réponse 3^5 = 243 5… encore la même coïncidence, mais elle ne tient pas en général. La méthode, en trois gestes : 1. trouver k tel que a^k 1 (Fermat, ou à la main) · 2. diviser l'exposant par k · 3. ne garder que a^{reste}, et le réduire. Elle ramène n'importe quel exposant à un calcul de collège.