Comment tester la primalité d'un nombre ?

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

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

Exemple corrigé

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 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é

Exemple corrigé

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é