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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Euclide

En arithmétique, le théorème d'Euclide sur les nombres premiers affirme :

Il existe une infinité de nombres premiers.

La première preuve écrite retrouvée de ce résultat figure dans les Éléments d'Euclide, proposition 20 du livre IX[1].

Plusieurs démonstrations existent.

Démonstration d'Euclide[modifier | modifier le code]

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 : supposons que p_{1},p_{2},p_{3},\dotsc,p_{n} soit 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 N+1  ; or, tout nombre possède un facteur premier, donc il existe un nombre premier qui ne fait pas partie de la suite donnée. Le résultat selon lequel tout nombre possède un facteur premier est prouvé dans les propositions 31 et 32 du livre VII des Éléments et découle aujourd'hui directement du théorème fondamental de l'arithmétique.

L'argumentation utilisée par Euclide permet de construire par récurrence une suite injective (p_{n}) de nombres premiers : p_{n} est défini comme le plus petit facteur premier de 1+\prod_{k<n}p_k. Mullin s'est demandé si la suite (p_{n}) ainsi obtenue parcourait tous les nombres premiers[3]. On ignore la réponse à cette question[4]. En revanche, si l'on prend pour p_{n} le plus grand facteur premier de 1+\prod_{k<n}p_{k}, alors on sait qu'une infinité de nombre premiers ne font pas partie de la suite (p_{n})[5].

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[6].

Comme le remarque Gérald Tenenbaum[7], la preuve d'Euclide « est trop simple pour être ineffective ». De fait, la construction montre que le n-ième nombre premier p_{n} est inférieur ou égal à 2^{2^{n}}. D'après Michael Hardy, ce n'est pas une démonstration par l'absurde[8].

Démonstration d'Euler[modifier | modifier le code]

Euler

Une autre preuve fut proposée par le mathématicien suisse Leonhard Euler. Cette démonstration s'appuie sur le théorème fondamental de l'arithmétique. Si P désigne l'ensemble des nombres premiers, Euler écrit :

\prod_{p\in P} \frac{1}{1-1/p}=\prod_{p\in P} \sum_{k\geq 0} \frac{1}{p^k}=\sum_n\frac{1}{n}

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 :

\prod_{p\in P} \sum_{k\geq 0} \frac{1}{p^k}=\sum_{k\geq 0} \frac{1}{2^k}\times\sum_{k\geq 0} \frac{1}{3^k}\times\sum_{k\geq 0} \frac{1}{5^k}\times\sum_{k\geq 0} \frac{1}{7^k}\times\cdots=\sum_n\frac{1}{n}

Dans le résultat obtenu, tous les produits possibles de nombres premiers apparaissent une fois ; c'est pourquoi d'après le théorème fondamental de l'arithmétique cette somme est une somme sur tous les entiers naturels.

La divergence de la série harmonique montre alors que la somme (à droite) tend vers l'infini : donc le produit (à gauche) ne peut être fini, il y a donc une infinité de nombres premiers.

La positivité des termes assure que toutes ces expressions ont bien un sens, même si elles sont potentiellement infinies.

Théorème de la progression arithmétique de Dirichlet[modifier | modifier le code]

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 ak+n, où a et n sont des entiers fixés, premiers entre eux. Autrement dit, il existe une infinité de nombres premiers dans toute progression arithmétique.

Le théorème d'Euclide correspond au cas où 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[modifier | modifier le code]

Ce théorème, conjecturé au début du XIXe 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. Soit \pi(x) le nombre des premiers inférieurs à un nombre x, le théorème d'Euclide dit que \pi(x) tend vers l'infini quand x croît. Le théorème des nombres premiers précise que la quantité \pi(x)/x est équivalente à 1/{\log (x)} quand x croît.

Autrement dit[9], le n-ième nombre premier noté p_n est à peu près de l'ordre de grandeur de n\log(p_{n}) ou encore \log(p_{n})/(p_{n}) est de l'ordre de grandeur de 1/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 Dirichlet, sont aussi connues.

Article détaillé : Théorème des nombres premiers.

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Euclide, Éléments, Livre IX, proposition 20.
  2. Euclide, Les Éléments, traduction, commentaires et notes de Bernard Vitrac [détail des éditions], vol. 2, p. 444-446.
  3. A. A. Mullin, Recursive function theory (a modern look at a Euclidean idea, Bull. Amer. Math. Soc., 69, (1963), 737
  4. Shanks a conjecturé que la réponse était positive. D. Shanks, Euclid's primes, Bull. Inst. Combin. Appl. 1 (1991), 33-36
  5. A. Booker, On Mullin's second sequence of primes, Integers 12A (2012)
  6. (en) « Kummer's Restatement of Euclid's Proof », sur The Prime Pages.
  7. Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres [détail des éditions], p. 10.
  8. (en) Michael Hardy et Catherine Woodgold, « Prime Simplicity », The Mathematical Intelligencer, vol. 31, no 4,‎ 2009, p. 44-52 (DOI 10.1007/s00283-009-9064-8).
  9. Gérald Tenenbaum et Michel Mendès France, Les Nombres premiers, Que sais-je ? 571, Paris, PUF, 1997, p. 11.