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é

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

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

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

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

Exercice d'exemple

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

1

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

2

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

3

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

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 tester la primalité d'un nombre ?

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, passons aux 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é