Nombres premiers

Deux diviseurs, pas un de plus

Un entier $n > 1$ est premier lorsqu'il a exactement deux diviseurs positifs : $1$ et $n$ lui-même. Les premiers nombres premiers sont $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$.

Un entier $n > 1$ qui n'est pas premier est dit composé : il s'écrit comme produit de deux entiers tous deux strictement plus petits que lui. $9 = 3 \times 3$, $15 = 3 \times 5$, $16 = 2 \times 8$ sont composés.

Attention au piège. $1$ n'est pas premier. Il n'a qu'un seul diviseur positif, lui-même, et la définition en demande deux. Ce n'est pas un caprice de vocabulaire : si $1$ était premier, la décomposition en facteurs premiers de la leçon suivante ne serait plus unique, parce qu'on pourrait coller autant de $1$ qu'on veut devant n'importe quel produit.

$2$ est le seul nombre premier pair : tout autre pair a $2$ pour diviseur, en plus de $1$ et de lui-même, donc au moins trois diviseurs.

Reconnaître un nombre premier

Pour tester un nombre $n$, on cherche un diviseur entre $2$ et le plus grand entier $k$ tel que $k \times k$ ne dépasse pas $n$. S'il n'y en a aucun, $n$ est premier. On s'arrête là parce que les diviseurs vont par paires : si $n$ avait un diviseur plus grand que $k$, le complément $n/k$ serait plus petit, et on l'aurait déjà trouvé.

Exemple. Pour $29$, $5 \times 5 = 25$ ne dépasse pas $29$, mais $6 \times 6 = 36$ le dépasse. Il suffit de tester $2$, $3$ et $5$. Aucun ne divise $29$, donc $29$ est premier. Pour $27$, $3$ divise $27$ et $3 \times 3 = 9 < 27$ : $27$ est composé, sans aller plus loin.

Un contrôle utile. N'utilisez le critère « il est impair » que pour éliminer les pairs. Être impair ne rend pas premier : $9$, $15$, $21$, $25$, $27$, $33$ sont impairs et composés. C'est le test jusqu'au carré qui tranche, pas la parité.

Le crible d'Ératosthène

Pour lister tous les premiers jusqu'à une borne, on n'a pas besoin de tester chaque entier séparément. On écrit les entiers de $2$ à la borne, et on raye au fur et à mesure les multiples de chaque premier déjà trouvé. Ce qui n'est jamais rayé est premier.

On s'arrête de rayer dès que le prochain premier $p$ vérifie $p^2$ plus grand que la borne : tous les composés restants ont déjà un facteur plus petit, et ont donc déjà été rayés.

Ce que cette leçon prépare. Tout entier $n > 1$ s'écrit comme produit de nombres premiers, et d'une seule façon : c'est le théorème fondamental de l'arithmétique, et c'est l'objet de la leçon suivante. Les critères de divisibilité servent ici d'accélérateur : pour tester $91$, le critère de $7$ n'existe pas dans la leçon précédente, mais $7 \times 13 = 91$ se voit dès qu'on essaie $7$, qui est plus petit que $10$ car $10 \times 10 = 100 > 91$.