En appliquant le test de Fermat : si $a^{n-1} \not\equiv 1 \pmod{n}$ pour un entier $a$ avec $\mathrm{pgcd}(a,n)=1$ , alors $n$ est composé

Approfondissement — Appliquer le test de Fermat pour détecter qu'un entier est composé sans factorisation complète.

Hors programme — Cette méthode va au-delà du B.O. officiel. Proposée pour aller plus loin.

L'objectif

Approfondissement — Appliquer le test de Fermat pour détecter qu'un entier est composé sans factorisation complète.

Le principe

Contraposée du petit théorème de Fermat : si $n$ est premier et $\mathrm{pgcd}(a,n)=1$ , alors $a^{n-1} \equiv 1 \pmod{n}$ ; donc si $a^{n-1} \not\equiv 1 \pmod{n}$ , $n$ est nécessairement composé.

La méthode

1
Choisir un entier $a$ avec $1 < a < n$ et vérifier que $\mathrm{pgcd}(a,n)=1$ (si $\mathrm{pgcd}(a,n)>1$ , on a directement un diviseur de $n$ ).
2
Calculer $a^{n-1} \pmod{n}$ par exponentiation rapide (décomposition binaire de $n-1$ ).
Comment appliquer le petit théorème de Fermat ?Voir
3
Si $a^{n-1} \not\equiv 1 \pmod{n}$ : conclure que $n$ est composé ( $a$ est un « témoin de Fermat »). Si $a^{n-1} \equiv 1 \pmod{n}$ : on ne peut pas conclure (possible nombre de Carmichael).

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Exemple 1 — Tester $n=15$ avec $a=2$

Étape 1 —

Choisir un entier

a

avec

1 < a < n

et vérifier que

\mathrm{pgcd}(a,n)=1

(si

\mathrm{pgcd}(a,n)>1

, on a directement un diviseur de

n

$\mathrm{pgcd}(2,15)=1$ , le test s'applique.

Étape 2 —

Calculer

a^{n-1} \pmod{n}

par exponentiation rapide (décomposition binaire de

n-1

Calculer $2^{14} \pmod{15}$ : $2^4=16 \equiv 1 \pmod{15}$ , donc $2^{12} \equiv 1$ et $2^{14} = 2^{12} \cdot 2^2 \equiv 4 \pmod{15}$ .

Étape 3 —

a^{n-1} \not\equiv 1 \pmod{n}

: conclure que

n

est composé (

a

est un « témoin de Fermat »). Si

a^{n-1} \equiv 1 \pmod{n}

: on ne peut pas conclure (possible nombre de Carmichael).

$2^{14} \equiv 4 \neq 1 \pmod{15}$ , donc $15$ est composé (et effectivement $15=3 \times 5$ ).

Application guidée

Exemple 2 — Tester $n=35$ avec $a=2$

Application autonome 1

Exemple 3 — Tester $n=9$ avec $a=2$

Application autonome 2

Exemple 4 — Tester $n=341$ avec $a=2$ (nombre de Poulet)

Application autonome 3

Exemple 5 — Tester $n=77$ avec $a=2$

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

En appliquant le test de Fermat : si an−1≢1(modn)a^{n-1} \not\equiv 1 \pmod{n}an−1≡1(modn) pour un entier aaa avec pgcd(a,n)=1\mathrm{pgcd}(a,n)=1pgcd(a,n)=1, alors nnn est composé

Pour comprendre, fais des exercices !

En appliquant le test de Fermat : si $a^{n-1} \not\equiv 1 \pmod{n}$ pour un entier $a$ avec $\mathrm{pgcd}(a,n)=1$ , alors $n$ est composé