Nombres premiers et petit théorème de Fermat (Terminale)

Q: Comment savoir rapidement si un nombre est premier ?

Il suffit de tester sa divisibilité par les nombres premiers inférieurs ou égaux à \sqrt{n}. Si aucun ne divise n, alors n est premier. Par exemple, pour 211, on teste 2, 3, 5, 7, 11 et 13 car 14^2=196 \leqslant 211<225=15^2 : aucun ne divise 211, qui est donc premier.

Q: Pourquoi y a-t-il une infinité de nombres premiers ?

Si les nombres premiers étaient en nombre fini, p_1, \dots, p_k, l'entier N=p_1p_2\cdots p_k+1 aurait un diviseur premier p_i de la liste. Ce p_i diviserait alors N-p_1\cdots p_k=1, ce qui est impossible. Attention : N lui-même n'est pas forcément premier.

Q: À quoi sert le petit théorème de Fermat ?

Il permet de calculer très vite le reste d'une grande puissance modulo un nombre premier p : on remplace l'exposant par son reste dans la division par p-1. Il sert aussi à prouver qu'un nombre n'est pas premier (témoin de Fermat) et il est au cœur du chiffrement RSA.

Ce chapitre d'arithmétique de Terminale maths expertes est consacré aux nombres premiers, les briques de base des entiers. Tu y démontres qu'il en existe une infinité, tu apprends à décomposer un entier en facteurs premiers et tu découvres le petit théorème de Fermat, outil clé pour calculer des restes de grandes puissances et comprendre le chiffrement RSA.

Définitions

Un entier naturel $p$ est premier s'il admet exactement deux diviseurs positifs : $1$ et $p$ . Ainsi $1$ n'est pas premier et $2$ est le seul nombre premier pair.
Un entier $n \geqslant 2$ non premier est dit composé : il s'écrit $n=ab$ avec $1<a<n$ et $1<b<n$ .
Le crible d'Ératosthène consiste à barrer successivement les multiples stricts de $2$ , $3$ , $5$ , $7$ , ... ; pour lister les nombres premiers jusqu'à $N$ , il suffit de traiter les nombres premiers $p$ tels que $p^2 \leqslant N$ , et les nombres restants sont premiers.
Un entier $a$ avec $1 \leqslant a \leqslant n-1$ est un témoin de non-primalité de $n$ lorsque $a^{n-1} \not\equiv 1\ [n]$ .

Propriétés

Tout entier $n \geqslant 2$ admet un diviseur premier ; si $n$ n'est pas premier, il admet un diviseur premier $p$ tel que $p^2 \leqslant n$ .
L'ensemble des nombres premiers est infini (démonstration d'Euclide avec $N=p_1p_2\cdots p_k+1$ ).
Lemme d'Euclide : si un nombre premier $p$ divise un produit $ab$ , alors $p$ divise $a$ ou $p$ divise $b$ .
Tout entier $n \geqslant 2$ se décompose de façon unique (à l'ordre près) en produit de facteurs premiers.
Petit théorème de Fermat : si $p$ est premier et ne divise pas $a$ , alors $a^{p-1} \equiv 1\ [p]$ .

Formules à retenir

Décomposition : $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ , et $n$ possède $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$ diviseurs positifs.
Le PGCD de deux entiers s'obtient en gardant les facteurs premiers communs avec le plus petit exposant, par exemple $\mathrm{PGCD}(3960\,;\,1386)=2\times 3^2\times 11=198$ .
Pour tout entier $a$ et tout nombre premier $p$ : $a^p \equiv a\ [p]$ .
Si $p$ est premier et $N=(p-1)q+r$ , alors $a^N \equiv a^r\ [p]$ pour tout $a$ non divisible par $p$ .

Exemple corrigé

Déterminer le reste de la division euclidienne de $3^{2026}$ par $11$ .

$11$ est un nombre premier qui ne divise pas $3$ : d'après le petit théorème de Fermat, $3^{10} \equiv 1\ [11]$ .
On effectue la division euclidienne de l'exposant par $10$ : $2026=10\times 202+6$ .
Donc $3^{2026}=\left(3^{10}\right)^{202}\times 3^6 \equiv 1^{202}\times 3^6 \equiv 3^6\ [11]$ .
Or $3^6=729=11\times 66+3$ , donc $3^6 \equiv 3\ [11]$ .
Conclusion : le reste de la division de $3^{2026}$ par $11$ est $3$ .

Ce que tu sauras faire

Savoir démontrer que l'ensemble des nombres premiers est infini
Savoir tester la primalité d'un entier $n$ en cherchant ses diviseurs premiers jusqu'à $\sqrt{n}$
Savoir utiliser le crible d'Ératosthène pour lister les nombres premiers
Savoir décomposer un entier en produit de facteurs premiers et en déduire ses diviseurs et un PGCD
Savoir appliquer le petit théorème de Fermat pour calculer le reste d'une grande puissance
Savoir utiliser un témoin de non-primalité et comprendre le principe du chiffrement RSA

Questions fréquentes

Comment savoir rapidement si un nombre est premier ?

Il suffit de tester sa divisibilité par les nombres premiers inférieurs ou égaux à $\sqrt{n}$ . Si aucun ne divise $n$ , alors $n$ est premier. Par exemple, pour $211$ , on teste $2$ , $3$ , $5$ , $7$ , $11$ et $13$ car $14^2=196 \leqslant 211<225=15^2$ : aucun ne divise $211$ , qui est donc premier.

Pourquoi y a-t-il une infinité de nombres premiers ?

Si les nombres premiers étaient en nombre fini, $p_1, \dots, p_k$ , l'entier $N=p_1p_2\cdots p_k+1$ aurait un diviseur premier $p_i$ de la liste. Ce $p_i$ diviserait alors $N-p_1\cdots p_k=1$ , ce qui est impossible. Attention : $N$ lui-même n'est pas forcément premier.

À quoi sert le petit théorème de Fermat ?

Il permet de calculer très vite le reste d'une grande puissance modulo un nombre premier $p$ : on remplace l'exposant par son reste dans la division par $p-1$ . Il sert aussi à prouver qu'un nombre n'est pas premier (témoin de Fermat) et il est au cœur du chiffrement RSA.