Puissance modulo p

Énoncé

Calculer 3¹⁰⁰ mod 7.

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

Correction

  1. Étape 1 : 3¹⁰⁰ 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⁶ ≡ 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¹⁰⁰ = 3⁶ × ¹⁶ ⁺ ⁴ = (3⁶)¹⁶ × 3⁴

  5. Étape 5 : Le premier facteur vaut 1¹⁶ = 1, donc il ne reste que 3⁴ :

    3¹⁰⁰ ≡ 3⁴ = 81 7

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

    81 = 7 × 11 + 4 ⟹ 3¹⁰⁰ ≡ 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 = 6×16+4 est un EXPOSANT : il faut encore calculer 3⁴ = 81, puis réduire modulo 7. Répondre « 3¹⁰⁰ ≡ 4 car le reste est 4 » tombe juste ici par pure coïncidence — 81 ≡ 4 aussi. Avec 3¹⁰¹, le reste serait 5 et la réponse 3⁵ = 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ᵏ ≡ 1 (Fermat, ou à la main) · 2. diviser l'exposant par k · 3. ne garder que aʳᵉˢᵗᵉ, et le réduire. Elle ramène n'importe quel exposant à un calcul de collège.