Théorème d'Euclide sur les nombres premiers

En arithmétique, le théorème d'Euclide sur les nombres premiers affirme qu'il existe une infinité de nombres premiers.

Euclide tel qu'imaginé par Joos van Wassenhove en 1474

Ce résultat est énoncé et démontré dans les Éléments d'Euclide, c'est la proposition 20 du livre IX. Il y prend cependant une forme différente : « les nombres premiers sont plus nombreux que n'importe quelle multitude de nombres premiers proposée »^[1], plus compatible avec la conception de l'infini de l'auteur.

D'autres preuves ont ensuite été proposées, notamment par Euler. Des résultats plus fins ont aussi été démontrés comme le théorème des nombres premiers sur la distribution asymptotique des nombres premiers.

Démonstration d'Euclide

Dans ses Éléments, Euclide démontre que de l'existence de trois nombres premiers distincts peut se déduire l'existence d'un quatrième. La démonstration se généralise immédiatement à toute énumération finie de nombres premiers. Il déduit que « les nombres premiers sont plus nombreux que toute multitude de nombres premiers proposée »^[2] . L'infini mis en évidence par cette preuve est donc un « infini potentiel », compatible avec la doctrine aristotélicienne. Cette démonstration directe n'est pas une démonstration par l'absurde, contrairement à ce qui a été souvent affirmé^[3].

Actualisée, sa démonstration se présente comme suit : soit ${\displaystyle q_{1},q_{2},q_{3},\dotsc ,q_{n}}$ une liste finie de nombres premiers distincts. Si ${\displaystyle N}$ désigne leur produit, les nombres premiers déjà énumérés ne peuvent pas diviser ${\displaystyle S=N+1}$ ; or un tel nombre entier ${\displaystyle S>1}$ possède un diviseur premier, qui ne fait donc pas partie de la liste donnée.

Le fait que que tout nombre entier ${\displaystyle S>1}$ possède un diviseur premier est énoncé par Euclide à la proposition 31 du livre VII des Éléments et il le démontre par descente infinie^[4]. On peut aussi le démontrer ainsi : ${\displaystyle q}$ le plus petit diviseur strictement supérieur à 1 de l'entier ${\displaystyle S}$ est nécessairement premier, car tout diviseur de ${\displaystyle q}$ est un diviseur de ${\displaystyle S}$, donc est égal à 1 ou ${\displaystyle q}$^[5],[6].

Applications de la technique utilisée par Euclide dans sa démonstration

Suite d'Euclide-Mullin

L'argumentation utilisée par Euclide permet de construire par récurrence une suite injective ${\displaystyle (q_{n})}$ de nombres premiers dite suite d'Euclide-Mullin : on pose ${\displaystyle q_{1}=2}$ et ${\displaystyle q_{n}}$ est défini comme le plus petit facteur premier de ${\displaystyle 1+\prod _{k<n}q_{k}}$.

Mullin s'est demandé si la suite ${\displaystyle (q_{n})}$ ainsi obtenue parcourait tous les nombres premiers^[7]. En 2017, on ignore la réponse à cette question^[8]. En revanche, si l'on prend pour ${\displaystyle q_{n}}$ le plus grand facteur premier de ${\displaystyle 1+\prod _{k<n}q_{k}}$, alors on sait qu'une infinité de nombres premiers ne font pas partie de la suite ${\displaystyle (q_{n})}$^[9].

Cas particuliers du théorème de la progression arithmétique

Sur le modèle de la démonstration d'Euclide, on peut démontrer qu'il existe une infinité de nombres premiers de la forme ${\displaystyle 4k+3}$ et aussi de la forme ${\displaystyle 6k+5}$^[10].

Dans le premier cas, on considère une liste ${\displaystyle q_{1},q_{2},q_{3},\dotsc ,q_{n}}$ de premiers de la forme ${\displaystyle 4k+3}$ et on montre que ${\displaystyle 4q_{1}\dots q_{n}+1}$ possède un diviseur premier de la forme ${\displaystyle 4k+3}$, différent des précédents.

Dans le deuxième cas, on considère de la même façon le nombre ${\displaystyle 6q_{1}\dots q_{n}-1}$.

Le théorème de la progression arithmétique de Dirichlet généralise ces résultats : il affirme qu'il y a une infinité de nombres premiers de la forme ${\displaystyle ak+b}$, où ${\displaystyle a}$ et ${\displaystyle b}$ sont des entiers fixés, premiers entre eux. Autrement dit, il existe une infinité de nombres premiers dans toute progression arithmétique de cette forme. La démonstration complète, qui s'inspire de celle d'Euler pour le théorème d'Euclide (voir ci-dessous), repose sur des arguments avancés d'analyse.

Application à une minoration de la fonction de compte des nombres premiers

De fait, comme le remarque Gérald Tenenbaum, la preuve d'Euclide « est trop simple pour être ineffective^[11] » : la construction permet de montrer que le n-ième nombre premier ${\displaystyle p_{n}}$ est inférieur ou égal à ${\displaystyle 2^{2^{n-1}}}$.

En effet, d'après le raisonnement d'Euclide, ${\displaystyle p_{n+1}\leqslant 2\times 3\times \cdots \times p_{n}+1\leqslant p_{n}^{n}+1}$.

Si l'on suppose que ${\displaystyle p_{n}\leqslant 2^{2^{n-1}}}$ pour ${\displaystyle n=1,2,\dots ,N}$, alors ${\displaystyle p_{N+1}\leqslant p_{1}p_{2}\dots p_{N}+1\leqslant 2^{1+2+\cdots +2^{N-1}}+1\leqslant 2^{2^{N}}}$, ce qui montre la propriété par récurrence.

On en déduit que la fonction ${\displaystyle \pi }$ de compte des nombres premiers vérifie ${\displaystyle \pi (x)\geqslant \log _{2}(\log _{2}(x))}$ pour ${\displaystyle x\geqslant 2.}$

Démonstration

Si ${\displaystyle 2^{2^{n-1}}\leqslant x<2^{2^{n}}}$, ${\displaystyle \pi (x)\geqslant \pi (2^{2^{n-1}})\geqslant \pi (p_{n})=n\geqslant \log _{2}(\log _{2}(x)}$.

Variante

Une variante de la démonstration d'Euclide a été donnée par le mathématicien allemand Ernst Kummer en retranchant 1 au produit au lieu d'ajouter 1^[12].

Démonstration d'Euler

Euler.

Une autre preuve fut proposée par le mathématicien suisse Leonhard Euler. Si ${\displaystyle {\mathcal {P}}}$ désigne l'ensemble des nombres premiers, Euler écrit :

${\displaystyle \prod _{p\in {\mathcal {P}}}{\frac {1}{1-1/p}}=\prod _{p\in {\mathcal {P}}}\sum _{k\geqslant 0}{\frac {1}{p^{k}}}=\sum _{n\geqslant 1}{\frac {1}{n}}}$.

Ces trois expressions représentent donc le même élément de [0, +∞]. La première égalité est donnée par la somme d'une série géométrique. Pour montrer la seconde égalité, il faut distribuer le produit par rapport à la somme. Dans le résultat obtenu, tous les produits (finis) possibles de nombres premiers apparaissent une fois ; d'après le théorème fondamental de l'arithmétique, ces produits sont tous les entiers supérieurs ou égaux à 1 :

${\displaystyle \prod _{p\in {\mathcal {P}}}\sum _{k\geqslant 0}{\frac {1}{p^{k}}}=\sum _{i\geqslant 0}{\frac {1}{2^{i}}}\times \sum _{j\geqslant 0}{\frac {1}{3^{j}}}\times \sum _{k\geq 0}{\frac {1}{5^{k}}}\times \sum _{l\geqslant 0}{\frac {1}{7^{l}}}\times \cdots =\sum _{i,j,k,l,\cdots \geqslant 0}{\frac {1}{2^{i}3^{j}5^{k}7^{l}\cdots }}=\sum _{n\geqslant 1}{\frac {1}{n}}}$.

La divergence de la série harmonique montre alors que la somme (à droite) est égale à +∞, donc le produit (à gauche) ne peut être fini. Il y a donc une infinité de nombres premiers.

Théorème des nombres premiers

Ce théorème, conjecturé au début du XIX^e siècle et prouvé en 1896, simultanément et indépendamment par Jacques Hadamard et Charles-Jean de La Vallée Poussin, précise la répartition des nombres premiers. Le théorème d'Euclide dit que la suite strictement croissante ${\displaystyle (p_{n})_{n\geq 1}}$ des nombres premiers est infinie. Le théorème des nombres premiers précise que ${\displaystyle p_{n}}$ est équivalent à ${\displaystyle n\ln n}$.

La démonstration originelle fait appel à des notions délicates d'analyse complexe, en particulier sur la fonction zêta de Riemann. Il existe aussi maintenant des démonstrations plus élémentaires. Des variantes, précisant en particulier le théorème de la progression arithmétique, sont aussi connues.

Dans d'autres anneaux

Tout nombre premier est un élément irréductible de l'anneau ℤ des entiers relatifs, c'est-à-dire qu'il n'est ni inversible (les seuls entiers inversibles sont 1 et –1), ni produit de deux entiers non inversibles. Les opposés des nombres premiers sont également irréductibles mais du point de vue de la divisibilité, on ne se préoccupe des nombres qu'à association près, c'est-à-dire à produit près par un inversible.

La démonstration d'Euclide (voir supra) repose essentiellement sur deux propriétés très simples de ℤ :

• c'est un anneau semi-primitif, c'est-à-dire que pour tout entier non nul n, il existe un entier k tel que 1 + kn ne soit pas inversible (par exemple k = |n|/n) ;
• c'est un anneau de Furstenberg, c'est-à-dire que tout entier S non nul et non inversible possède un diviseur irréductible (puisque |S| > 1).

Elle utilise aussi l'existence d'un entier N non nul et non inversible, c'est-à-dire le fait que l'anneau ℤ n'est pas un corps.

Le même raisonnement permet de démontrer que

dans tout anneau semi-primitif et de Furstenberg qui n'est pas un corps, il existe une infinité d'éléments irréductibles et deux à deux premiers entre eux donc non associés^[13].

Ce théorème s'applique par exemple^[14] à l'anneau ℝ[X] des polynômes à coefficients réels ou à l'anneau ℤ[i] des entiers de Gauss^[15], mais aussi à certains anneaux non euclidiens comme ℤ[(1 + i√19)/2], voire non principaux comme^[15] ℤ[X] ou ℝ[X, Y], ou même non factoriels comme l'anneau ℝ[cos, sin] des polynômes trigonométriques ou l'anneau ℂ[T², T³] des fonctions régulières sur la cubique cuspidale d'équation y² = x³ (il n'est même pas intégralement clos ni semi-factoriel).

Dans cette démonstration d'Euclide, les trois hypothèses sont utiles :

• il faut avant tout que l'anneau ne soit pas un corps, car dans un corps il n'y a pas d'élément irréductible ;
• jointe à l'hypothèse précédente, l'hypothèse supplémentaire « de Fürstenberg » garantit l'existence d'irréductibles. Elle est indispensable car certains anneaux qui ne sont pas des corps n'ont pourtant pas d'irréductibles^[16]. C'est le cas de l'anneau des entiers algébriques^[17], qui est par ailleurs semi-primitif^[18] ;
• la semi-primitivité est aussi primordiale, car il existe des anneaux atomiques (donc de Furstenberg) qui n'ont qu'un nombre fini d'irréductibles (à association près)^[19]. Exemples qui sont même principaux : un corps, un anneau de valuation discrète, ou encore l'anneau (ℤ\⟨2, 3⟩)⁻¹ℤ des fractions d'entiers dont le dénominateur n'est divisible ni par 2, ni par 3.

Cependant, une autre méthode permet de démontrer qu'un anneau qui n'a qu'un nombre fini d'irréductibles (à association près) est principal dès qu'il est factoriel^[20] donc par contraposition,

tout anneau factoriel non principal a une infinité d'irréductibles deux à deux non associés.

Ce théorème s'applique par exemple aux anneaux ℤ[X] et ℝ[X, Y] déjà cités mais aussi à des anneaux factoriels (donc atomiques) non semi-primitifs, comme^[21] l'anneau ℚ[X, Y]_{⟨X, Y⟩} des fractions rationnelles en X, Y à coefficients rationnels dont le dénominateur est un polynôme à terme constant non nul.