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}$

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

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).

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Exemple 1 — Calculer $3^{100} \pmod{7}$

Étape 1 —

Vérifier que

p

est premier et que

p \nmid a

(condition d'application du théorème).

$p=7$ est premier et $7 \nmid 3$ , donc le théorème s'applique avec $a=3$ .

Étape 2 —

Effectuer la division euclidienne de l'exposant

n

par

p-1

: écrire

n = (p-1)q + r

avec

0 \leq r < p-1

Division euclidienne de $100$ par $p-1=6$ : $100 = 6 \times 16 + 4$ , donc $r=4$ .

Étape 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}

$3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 3^4 \equiv 3^4 \pmod{7}$ .

Étape 4 —

Calculer

a^r \pmod{p}

(exposant

r

petit, calcul direct ou par décompositions successives).

$3^4 = 81 = 7 \times 11 + 4$ , donc $3^{100} \equiv 4 \pmod{7}$ .

Application guidée

Exemple 2 — Calculer $2^{50} \pmod{11}$

Application autonome 1

Exemple 3 — Calculer $5^{77} \pmod{13}$

Application autonome 2

Exemple 4 — Calculer $7^{200} \pmod{17}$

Application autonome 3

Exemple 5 — Calculer $4^{1000} \pmod{23}$

Crée ton compte gratuit pour accéder à la fiche et aux exercices