Théorème d’Euclide sur l’infinité des nombres premiers : démonstration (preuve)

Théorème d’Euclide sur l’Infinité des Nombres Premiers
Contexte : Nombres Premiers

Un nombre premier est un entier naturel supérieur à 1 qui n’est divisible que par 1 et par lui-même. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13, etc.

Le théorème fondamental de l’arithmétique nous apprend que tout entier supérieur à 1 est soit un nombre premier, soit un produit unique de nombres premiers. Cela fait des nombres premiers les « atomes » de l’arithmétique. Une question naturelle est de savoir si cette liste d’atomes est finie ou infinie.

Théorème d’Euclide (circa 300 av. J.-C.)

Il existe une infinité de nombres premiers.

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.