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

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.

Plusieurs démonstrations existent.

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.

Actualisée, sa démonstration se présente comme suit : supposons que $p_1,p_2,p_3,...,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.$

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^{[réf. nécessaire]}.

Comme le remarque Gérald Tenenbaum, la preuve d'Euclide « est trop simple pour être ineffective ». De fait, la construction montre que le $n$^e nombre premier $p_n$ est inférieur ou égal à $2^{2^n}$.

Démonstration d'Euler

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}$

On utilise pour cela la somme d'une série géométrique et le développement (unique) en facteurs premiers d'un entier naturel (autrement dit, le théorème fondamental de l'arithmétique). 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.

Théorème de la progression arithmétique de Dirichlet

Article détaillé : Théorème de la progression arithmétique.

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

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. 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, le $n$^e 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

• Démonstration de Fürstenberg de l'infinité des nombres premiers
• Preuve grâce à la densité de Schnirelmann