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

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

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

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 trois nombres premiers distincts peut se déduire 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 en nombre plus important que toute quantité finie. L'infini mis en évidence par cette preuve est donc un « infini potentiel », compatible avec la doctrine aristotélicienne^[2].

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 N désigne leur produit, les nombres premiers déjà énumérés ne peuvent pas diviser S = N + 1 ; or un tel nombre entier S > 1 possède un diviseur premier, qui ne fait donc pas partie de la suite donnée. Euclide énonce à la proposition 31 du livre VII des Éléments que tout nombre entier S > 1 possède un diviseur premier et le démontre par descente infinie^[3]. On peut aussi le démontrer ainsi : q le plus petit diviseur strictement supérieur à 1 de l'entier S est nécessairement premier, car tout diviseur de q est un diviseur de S, donc est égal à 1 ou q^[4],[5].

L'argumentation utilisée par Euclide permet de construire par récurrence une suite injective ${\displaystyle (q_{n})}$ de nombres premiers : ${\displaystyle q_{n}}$ est défini comme le plus petit facteur premier de ${\displaystyle 1+\prod _{k<n}q_{k}}$. Cette démonstration directe n'est donc pas une démonstration par l'absurde, contrairement à ce qui a été souvent affirmé^[6]. De fait, comme le remarque Gérald Tenenbaum, la preuve d'Euclide « est trop simple pour être ineffective^[7] » : 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}}}$.

Mullin s'est demandé si la suite ${\displaystyle (q_{n})}$ ainsi obtenue parcourait tous les nombres premiers^[8]. En 2017, on ignore la réponse à cette question^[9]. 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})}$^[10].

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

Démonstration d'Euler

Euler.

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

${\displaystyle \prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{n\geq 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 P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{i\geq 0}{\frac {1}{2^{i}}}\times \sum _{j\geq 0}{\frac {1}{3^{j}}}\times \sum _{k\geq 0}{\frac {1}{5^{k}}}\times \sum _{l\geq 0}{\frac {1}{7^{l}}}\times \cdots =\sum _{i,j,k,l,\cdots \geq 0}{\frac {1}{2^{i}3^{j}5^{k}7^{l}\cdots }}=\sum _{n\geq 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 de la progression arithmétique de Dirichlet

Le théorème de Dirichlet généralise le résultat d'Euclide : il affirme qu'il y a une infinité de nombres premiers de la forme ${\displaystyle ak+n}$, où ${\displaystyle a}$ et ${\displaystyle n}$ 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.

Le théorème d'Euclide correspond au cas où ${\displaystyle a=1}$. Il existe des preuves élémentaires pour certains cas particuliers du théorème de Dirichlet, mais la démonstration complète, qui s'inspire de celle d'Euler pour le théorème d'Euclide, repose sur des arguments avancés d'analyse.

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^[12].

Ce théorème s'applique par exemple^[13] à l'anneau ℝ[X] des polynômes à coefficients réels ou à l'anneau ℤ[i] des entiers de Gauss^[14], mais aussi à certains anneaux non euclidiens comme ℤ[(1 + i√19)/2], voire non principaux comme^[14] ℤ[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^[15]. C'est le cas de l'anneau des entiers algébriques^[16], qui est par ailleurs semi-primitif^[17] ;
• 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)^[18]. 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^[19] 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^[20] 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.

Notes et références

1. Traduction inspirée de D. Joyce, Livre IX, proposition 20.
2. Euclide (trad. Bernard Vitrac), Les Éléments [détail des éditions], vol. 2, p. 444-446.
3. Euclide (trad. Bernard Vitrac), Les Éléments [détail des éditions], vol. 2, p 339-341, ou D. Joyce livre VII proposition 31.
4. Cette variante est également présente dans certains textes des Éléments Euclide (trad. Bernard Vitrac), Les Éléments [détail des éditions], vol. 2 p. 341.
5. Le résultat peut être utilisé pour une démonstration par récurrence de l'existence d'une décomposition en facteurs premiers, voir « Théorème fondamental de l'arithmétique ».
6. Ceci est étudié en détail dans (en) Michael Hardy et Catherine Woodgold, « Prime Simplicity », The Mathematical Intelligencer, vol. 31, n^o 4,‎ 2009, p. 44-52 (DOI 10.1007/s00283-009-9064-8), et résulte d'une confusion avec une autre preuve procédant par l'absurde : on suppose qu'il n'existe qu'un nombre fini de nombres premiers, soient p₁, …, p_n, et l'on aboutit à une contradiction par le même argument qu'Euclide, mais cette démonstration indirecte n'est pas dans Euclide.
7. Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres [détail des éditions], p. 10.
8. (en) A. A. Mullin, « Recursive function theory. (A modern look at a Euclidean idea) », Bull. Amer. Math. Soc., vol. 69,‎ 1963, p. 737 (DOI 10.1090/S0002-9904-1963-11017-4).
9. Shanks a conjecturé que la réponse était positive. (en) D. Shanks, « Euclid's primes », Bull. Inst. Combin. Appl., vol. 1, 1991, p. 33-36.
10. (en) A. Booker, On Mullin's second sequence of primes, Integers 12A (2012).
11. (en) « Kummer's Restatement of Euclid's Proof », sur The Prime Pages.
12. (en) Pete L. Clark, « The Euclidean criterion for irreducibles », The American Mathematical Monthly, vol. 124, n^o 3,‎ 2017, p. 198-216 (arXiv 1605.01298), théorème 2.3 (b).
13. (en) « Rings which are : commutative, atomic domain, semiprimitive, not field », sur Database of Ring Theory.
14. Clark 2017, théorème 2.4.
15. J. Coykendall, D. E. Dobbs et B. Mullins, « On integral domains with no atoms », Comm. Alg., vol. 27, n^o 12,‎ 1999, p. 5813-5831 (DOI 10.1080/00927879908826792).
16. Daniel Perrin, « Autour du ppcm et du pgcd », 1979, p. 6.
17. Clark 2017, exemple 4.7.
18. On les appelle les anneaux de Cohen-Kaplansky (Clark 2017, p. 12 du fichier arXiv).
19. Clark 2017, théorème 5.1.
20. (en) « Rings which are : commutative, unique factorization domain, not principal ideal domain, not semiprimitive », sur Database of Ring Theory.

Voir aussi

Articles connexes

• Démonstration de Furstenberg de l'infinitude de l'ensemble des nombres premiers
• Démonstration utilisant la densité de Schnirelmann
• Nombre premier primoriel
• Suite d'Euclide–Mullin

Liens externes

• (en) Richard J. Lipton et Ken Regan, « There Are Many Primes », sur Gödel's Lost Letter and P=NP, 8 janvier 2015
• (en) Alexander Bogomolny, « Infinitude of Primes », sur Cut The Knot — Relate 18 preuves.