Nombres premiers

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

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

Définition 1 On dit qu'un entier est un multiple d'un entier , ou que est un diviseur de lorsqu'il existe un entier tel que .

Définition 2 On dit qu'un entier $p\ge 2$ est premier lorsqu'il possède pour seuls diviseurs positifs 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 est un nombre premier alors que n'en est pas un. En revanche, les nombres négatifs étant autorisés dans la définition de «diviseurs», l'entier possède en tout et pour tout quatre diviseurs (à savoir , , et ).

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 l'ensemble des nombres premiers. est une partie de $\mathbb{N}$ , et est non vide car est premier. On va supposer finie et aboutir à une absurdité.

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

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

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