Utiliser le petit théorème de Fermat pour simplifier un calcul de puissance modulo un nombre premier.
Choisissez une approche :
En utilisant ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp) pour simplifier an(modp)a^n \pmod{p}an(modp) : écrire n=(p−1)q+rn = (p-1)q + rn=(p−1)q+r et obtenir an≡ar(modp)a^n \equiv a^r \pmod{p}an≡ar(modp)
Réduire le calcul de an(modp)a^n \pmod{p}an(modp) en effectuant la division euclidienne de nnn par p−1p-1p−1, puis en utilisant le petit théorème de Fermat.