Nombres premiers

On appelle entier (ou entier relatif, c'est-à-dire positif ou négatif) tout élément de

$$\mathbb{Z}=\big\{ \ldots, -3,-2,-1,\; 0,\; 1,\; 2,\; 3,\ldots \big\}$$

Définition 1   On dit qu'un entier $a$ est un multiple d'un entier $b$, ou que $b$ est un diviseur de $a$ lorsqu'il existe un entier $k$ tel que $a=kb$.

Définition 2   On dit qu'un entier $p\ge 2$ est premier lorsqu'il possède pour seuls diviseurs positifs $1$ et lui-même.

On notera au passage qu'au hasard des définitions, on parlera parfois d'entiers relatifs (les éléments de $\mathbb{Z}$) et parfois d'entiers naturels (les éléments de $\mathbb{N}$). Ce n'est qu'exceptionnellement très significatif ; la principale fonction est d'être cohérent avec le reste du monde. Ainsi, comme partout ailleurs, dans ce cours, le nombre $3$ est un nombre premier alors que $-3$ n'en est pas un. En revanche, les nombres négatifs étant autorisés dans la définition de «diviseurs», l'entier $3$ possède en tout et pour tout quatre diviseurs (à savoir $-3$, ${-1}$,$1$ et $3$).

Et tout de suite un joli théorème, qui remonte aux Éléments d'Euclide, écrits au IIIème siècle avant notre ère (c'est la proposition 20 du livre IX).

Théorème 1   Il existe une infinité de nombres premiers.

Vous connaissez probablement déjà une démonstration, il en existe plusieurs qui sont toutes bonnes à connaître, en voici une qui est très proche de celle du traité d'Euclide lui-même.

Démonstration : Soit $A$ l'ensemble des nombres premiers. $A$ est une partie de $\mathbb{N}$, et est non vide car $2$ est premier. On va supposer $A$ finie et aboutir à une absurdité.

Supposons donc $A$ finie. Dès lors que $A$ est une partie finie de $\mathbb{N}$, évidemment non vide car $2$ est premier, $A$ possède un plus grand élément. Notons $P$ ce plus grand élément, le mystérieux «plus grand nombre premier».

Considérons alors l'entier $N=P!+1$ (la factorielle de $P$, plus $1$). Pour tout entier $k$ tel que $2\leqslant k\le P$, comme $k$ divise $P!$ et ne divise pas $1$, $k$ ne peut diviser $N$. Tout diviseur de $N$, et en particulier tout diviseur premier de $N$, est donc strictement supérieur à $P$.

Or tout entier, et par exemple $N$, possède au moins un diviseur premier (pourquoi ? exercice...). Mais alors, chacun de ces diviseurs premiers contredit la maximalité de $P$. Absurdité !$\square$