Nombres premiers et arithmétique appliquée : cours de maths · Terminale expertes

Reconnaître un nombre premier

Un nombre premier est un entier naturel $p\geq2$ dont les seuls diviseurs positifs sont $1$ et $p$. Un entier $n\geq2$ qui n'est pas premier est composé. Ni $0$ ni $1$ n'est premier ; $2$ est le seul premier pair.

Tout entier $n\geq2$ a un diviseur premier. S'il est composé, il en a un inférieur ou égal à $\sqrt n$. Pour prouver sa primalité, tester tous les premiers jusqu'à cette borne incluse ; pour prouver qu'il est composé, un diviseur $d$ tel que $1<d<n$ suffit. Par exemple, $143=11\times13$.

Il existe une infinité de nombres premiers.

Voir un exemple — Vérifier que 139 est premier

Comme $11^2<139<12^2$, les facteurs premiers à tester sont $2,3,5,7,11$. Les restes de $139$ dans ces divisions sont respectivement $1,1,4,6,7$. Aucun n'est nul : aucun de ces nombres ne divise $139$, donc $139$ est premier.

Comprendre pourquoi — Pourquoi les nombres premiers sont en nombre infini

Si les premiers formaient une liste complète finie $p_1,\ldots,p_k$, $N=p_1\cdots p_k+1\ge2$ aurait un diviseur premier. Aucun $p_i$ ne divise $N$, car son reste modulo $p_i$ vaut $1$. Ce diviseur serait hors de la liste : contradiction. Cela n’affirme pas que $N$ est lui-même premier.

Décomposer et trouver les diviseurs

Tout entier naturel $n\geq2$ a une décomposition en facteurs premiers, unique à l'ordre des facteurs près :

n=p_1^{\alpha_1}\cdots p_k^{\alpha_k},\qquad p_i\text{ premiers distincts},\quad\alpha_i\geq1\text{ entiers}.

Diviser successivement par les facteurs premiers et regrouper leurs répétitions. Par exemple, $756=2^2\times3^3\times7$.

Ici, $1$ est représenté par un produit vide de valeur $1$. Pour un entier négatif, séparer le signe et décomposer sa valeur absolue. Zéro n'a pas de décomposition en facteurs premiers.

Les diviseurs positifs de $n$ sont exactement les produits $p_1^{\beta_1}\cdots p_k^{\beta_k}$ où $0\leq\beta_i\leq\alpha_i$ sont entiers. Pour le PGCD, garder les facteurs communs avec les plus petits exposants :

72=2^3\times3^2,\quad108=2^2\times3^3\quad\Longrightarrow\quad\operatorname{PGCD}(72,108)=2^2\times3^2=36.

Petit théorème de Fermat

Si $p$ est premier et $a\in\mathbb Z$, alors :

a^p\equiv a\pmod p.

Si, de plus, $p\nmid a$, alors $a^{p-1}\equiv1\pmod p$. Si $p\mid a$, cette puissance est congrue à $0$, pas à $1$.

Par exemple, $13$ est premier et $13\nmid5$, donc $5^{12}\equiv1\pmod{13}$. Comme $2026=12\times168+10$ et $5^2\equiv-1\pmod{13}$, on obtient $5^{2026}\equiv(5^2)^5\equiv12\pmod{13}$.

Vérifier une seule congruence de Fermat ne prouve pas qu'un entier est premier.

Lister les premiers par un crible

Pour lister les nombres premiers jusqu'à $N\geq2$, écrire les entiers de $2$ à $N$. Prendre le plus petit candidat non barré encore non traité et barrer ses multiples stricts. Recommencer pour les candidats premiers $p$ tels que $p^2\leq N$.

On peut commencer les exclusions à $p^2$. Les nombres restants sont exactement les premiers jusqu'à $N$. Si $N<2$, la liste est vide.

Voir un exemple — Effectuer un crible jusqu’à 30

Pour $N=30$, barrer d'abord les multiples stricts de $2$. Avec $3$, les nouvelles exclusions sont $9,15,21,27$. Avec $5$, on exclut $25$. Comme $\sqrt{30}<6$, les facteurs nécessaires sont tous traités.

Les nombres premiers restants sont $2,3,5,7,11,13,17,19,23,29$.

Comprendre pourquoi — Pourquoi le crible s’arrête à la racine carrée

Un premier n’est jamais barré : on barre seulement des multiples stricts. Chaque composé $m\le N$ a un diviseur premier $p\le\sqrt m\le\sqrt N$, donc il sera barré. Avant $p^2$, les multiples stricts de $p$ ont un facteur premier plus petit et sont déjà traités. Commencer à $p^2$ et arrêter quand $p^2>N$ suffit. Les listes sont finies ; pour $N<2$, la sortie est vide.