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 : 7 est premier et 7 3, donc 3^6 1 7.
2. Étape 2 : 100 = 6 16 + 4, donc 3^{100} = 3^{6 16 + 4} = (3^6)^{16} 3^4 1^{16} 3^4 = 81 7.
3. Étape 3 : 81 = 7 11 + 4, donc 3^{100} 4 7.

   3^{100} 4 7