Comment appliquer le petit théorème de Fermat ?

En utilisant $a^{p-1} \equiv 1 \pmod{p}$ pour simplifier $a^n \pmod{p}$ : écrire $n = (p-1)q + r$ et obtenir $a^n \equiv a^r \pmod{p}$

L'objectif

Calculer $a^n \pmod{p}$ rapidement en ramenant l'exposant à un reste modulo $p-1$ .

Le principe

Petit théorème de Fermat : si $p$ est premier et $p \nmid a$ , alors $a^{p-1} \equiv 1 \pmod{p}$ .

La méthode

1
Vérifier que $p$ est premier et que $p \nmid a$ (condition d'application du théorème).
2
Effectuer la division euclidienne de l'exposant $n$ par $p-1$ : écrire $n = (p-1)q + r$ avec $0 \leq r < p-1$ .
3
Factoriser : $a^n = a^{(p-1)q+r} = (a^{p-1})^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod{p}$ .
4
Calculer $a^r \pmod{p}$ (exposant $r$ petit, calcul direct ou par décompositions successives).

Difficulté croissante de 1 à 5

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

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)