Comment appliquer le petit… : En utilisant a^ p-1 equiv 1 pmod p pour… — maths expertes | MetMat

Reconnaître

Résoudre

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

Que ferais-tu face à un exercice de ce type ?

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

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, passons aux exercices.

Exercice d'exemple

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

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

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

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

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

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

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

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)

Pour comprendre, passons aux exercices.

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