Démonstration (par l’absurde)

La démonstration classique, telle qu’elle apparaît dans les Éléments d’Euclide, est un modèle de clarté et d’élégance.

1. Hypothèse par l’absurde : Supposons que l’ensemble des nombres premiers est fini. On peut donc les lister tous. Soit cette liste finie de nombres premiers : $P = \{p_1, p_2, p_3, \dots, p_n\}$.
2. Construction d’un nouvel entier : Considérons l’entier $N$ construit en faisant le produit de tous les nombres premiers de notre liste, auquel on ajoute 1 : $$ N = (p_1 \times p_2 \times p_3 \times \dots \times p_n) + 1 $$
3. Analyse de l’entier N : Cet entier $N$ est supérieur à 1. D’après le théorème fondamental de l’arithmétique, il doit être divisible par au moins un nombre premier. Ce diviseur premier doit appartenir à notre liste $P$, puisque nous avons supposé que cette liste contenait tous les nombres premiers.
4. La Contradiction : Soit $p_k$ ce diviseur premier de $N$ (avec $1 \le k \le n$).
   • Par construction, $p_k$ divise le produit $p_1 \times p_2 \times \dots \times p_n$.
   • Nous savons aussi que $p_k$ divise $N$.
   Si un nombre divise deux autres nombres, il doit aussi diviser leur différence. Par conséquent, $p_k$ doit diviser la différence : $$ N – (p_1 \times p_2 \times \dots \times p_n) = 1 $$ Nous arrivons à la conclusion que $p_k$ divise 1. C’est une contradiction, car un nombre premier est par définition strictement supérieur à 1.
5. Conclusion : L’hypothèse de départ, à savoir que l’ensemble des nombres premiers est fini, est donc fausse. Il doit exister une infinité de nombres premiers.

Remarques et Implications

• Cette preuve est non constructive : elle prouve qu’il y a une infinité de nombres premiers mais ne donne pas de méthode pour les trouver.
• Une erreur d’interprétation courante est de croire que le nombre $N$ construit dans la preuve est lui-même premier. Ce n’est pas toujours le cas. Par exemple, si l’on prend la liste des premiers jusqu’à 11 ({2, 3, 5, 7, 11}), le nombre $N = (2 \times 3 \times 5 \times 7 \times 11) + 1 = 2311$ est bien premier. Mais si l’on prend la liste {2, 3, 5, 7, 11, 13}, on a $N = 30031 = 59 \times 509$. La preuve dit simplement que les diviseurs premiers de $N$ (ici 59 et 509) ne peuvent pas être dans la liste de départ.
• Ce théorème a été le point de départ de nombreuses recherches sur la distribution et les propriétés des nombres premiers, menant à des résultats plus profonds comme le théorème des nombres premiers ou le théorème de Dirichlet.