Existe-t-il une infinité de nombres premiers ?

Oui. Euclide l'a démontré vers 300 avant J.-C. Peu importe combien de premiers tu réunis dans une liste, l'argument construit un nombre dont tous les facteurs premiers se situent en dehors de cette liste, donc au moins un nouveau premier doit exister.

La démonstration d'Euclide montre-t-elle que N = (p1 x p2 x ... x pk) + 1 est toujours premier ?

Non, et c'est l'erreur la plus courante dans l'énoncé de la démonstration. N doit seulement avoir un facteur premier absent de la liste, ce qui peut être N lui-même ou un nombre plus petit. Par exemple, 2x3x5x7x11x13 + 1 = 30031, qui n'est PAS premier : 30031 = 59 x 509. Or 59 et 509 sont des premiers absents de la liste {2,3,5,7,11,13}, donc la démonstration fonctionne parfaitement.

De quel type de démonstration s'agit-il ?

C'est une démonstration par l'absurde (reductio ad absurdum). On suppose le contraire de ce qu'on veut démontrer, à savoir qu'il n'existe qu'un nombre fini de premiers, puis on montre que cette hypothèse mène à une contradiction.

Comment la démonstration garantit-elle l'existence d'un premier hors de la liste ?

Le nombre N construit laisse un reste de 1 quand on le divise par n'importe quel premier de la liste, donc aucun premier listé ne divise N. Mais tout entier supérieur à 1 a au moins un facteur premier. Donc N a un facteur premier, et ce facteur ne peut pas être dans la liste. Un premier hors de la liste est garanti.

Ce résultat est-il lié à l'argument diagonal de Cantor ou au théorème de Goodstein ?

Tous les trois appartiennent à la même famille de résultats où une simple construction défait toute tentative de description finie (ou dénombrable) complète. Euclide défait toute liste finie de premiers, Cantor défait toute liste dénombrable de réels, et Goodstein produit une suite qui défait le pouvoir démonstratif de l'arithmétique de Peano.

La démonstration d'Euclide : il existe une infinité de nombres premiers

Quelque part vers 300 avant J.-C., Euclide a écrit un argument assez court pour tenir en un seul paragraphe. Il n'a jamais été amélioré, parce qu'il ne peut pas l'être. L'affirmation est que les nombres premiers se poursuivent indéfiniment, et la démonstration est une construction : donne-moi une liste finie quelconque de premiers, et je te remettrai un premier qui ne s'y trouve pas.

Deux mille ans plus tard, l'argument garde la qualité d'un bon tour de magie. Tu vois chaque étape clairement. Tu sais exactement comment ça se termine. Et ça fait toujours son effet.

Ce qu'est un premier, et pourquoi la question importe

Un nombre premier est un entier supérieur à 1 dont les seuls diviseurs sont 1 et lui-même. Les premiers sont : 2, 3, 5, 7, 11, 13. Ils se situent dans les entiers comme des atomes : tout autre entier est construit en multipliant des premiers. Le nombre 30, par exemple, se décompose en 2 fois 3 fois 5, et il n'y a essentiellement qu'une seule façon d'effectuer cette factorisation.

Étant donné que les premiers sont les briques élémentaires de tous les entiers, il est naturel de se demander : s'épuisent-ils ? Existe-t-il un plus grand premier, au-delà duquel le puits est à sec ? La réponse d'Euclide est non, et le chemin qu'il emprunte est assez élégant pour être suivi en une seule séance.

La mise en place : supposons que la liste est complète

L'argument est une démonstration par l'absurde. On commence par accorder à l'opposition tout ce qu'elle veut.

Supposons qu'il n'existe qu'un nombre fini de premiers

Supposons, pour l'argument, que la collection complète de tous les premiers est une liste finie : p1, p2, p3, jusqu'à pk. Aucun premier n'existe en dehors de cette liste. C'est l'hypothèse que nous allons détruire.

Maintenant, ayant rassemblé tous les premiers qui existent dans cette liste, construisons un nouveau nombre à partir d'eux.

Construire le nombre qui brise la liste

Former N en multipliant tous les premiers listés et en ajoutant 1

Soit N = (p1 fois p2 fois p3 fois ... fois pk) + 1. C'est-à-dire : prendre le produit de chaque premier de la liste supposément complète, puis ajouter 1.

C'est le geste clé, et cela vaut la peine de ralentir pour voir ce qu'il fait. Multiplier tous les premiers listés donne un nombre que chaque premier de la liste divise exactement. Ajouter 1 les perturbe tous en même temps.

Quand tu divises N par p1, tu obtiens un reste de 1, parce que le produit (p1 fois p2 fois ... fois pk) est divisible par p1, et ajouter 1 décale le reste à 1. La même logique s'applique à p2, à p3, à chaque premier de la liste. Aucun d'eux ne divise N exactement.

La contradiction

N a un facteur premier, mais ce facteur ne peut pas être dans la liste

Tout entier supérieur à 1 a au moins un facteur premier. C'est une conséquence du théorème fondamental de l'arithmétique : continue à factoriser jusqu'à ne plus pouvoir, et il ne te reste que des premiers. Donc N a un facteur premier. Appelons-le q.

Nous venons de montrer qu'aucun premier de la liste ne divise N. Donc q n'est pas dans la liste. Mais nous avons supposé que la liste contenait tous les premiers. C'est la contradiction : nous avons trouvé un premier, q, qui ne se trouve pas dans la liste supposément complète.

L'hypothèse doit être fausse

Puisque l'hypothèse qu'il n'existe qu'un nombre fini de premiers mène directement à une contradiction, l'hypothèse est fausse. Il n'existe aucune liste finie qui contienne tous les premiers. Les premiers se poursuivent indéfiniment.

L'exemple qui rend la démonstration honnête

C'est là que beaucoup de présentations populaires de la démonstration d'Euclide s'égarent. Elles prétendent que N lui-même est toujours premier. Il ne l'est pas, et la distinction importe.

Prends la liste 13. Le produit est 2 fois 3 fois 5 fois 7 fois 11 fois 13, ce qui donne 30030. Ajoute 1 et tu obtiens N = 30031.

30031 est-il premier ? Non.

30031 = 59 fois 509.

Or 59 et 509 sont premiers, et aucun des deux n'apparaît dans la liste 13. C'est exactement ce que la démonstration prédit : non pas que N est premier, mais que les facteurs premiers de N sont absents de la liste. Dans ce cas, les facteurs premiers sont 59 et 509, deux premiers qui ont été omis de la liste finie. L'argument est validé, mais la validation vient des facteurs, pas de N lui-même.

Ce que la démonstration dit vraiment

Il vaut la peine de s'arrêter sur la forme de l'argument, car elle est inhabituellement propre.

Tu ne construis pas le premier manquant explicitement. Tu ne le cherches pas. Tu prouves qu'il doit exister en montrant que supposer le contraire mène à une impasse logique. Le premier q qui se cache dans les facteurs de N peut être facile à trouver (comme le sont 59 et 509, si tu essaies quelques petits diviseurs de 30031) ou il peut être énorme. La démonstration s'en moque. Sa force vient de l'inévitabilité : quelle que soit la liste que tu remets, la construction trouve une lacune.

Cela rejoint naturellement d'autres démonstrations qui procèdent dans le même esprit de « suppose le contraire, regarde-le s'effondrer ». L'argument diagonal de Cantor utilise la même structure à plus grande échelle : suppose qu'une liste complète de réels existe, puis construis un réel prouvablement absent d'elle. L'écho d'Euclide est indéniable.

Pourquoi les premiers ne s'épuisent jamais complètement

Une chose que la démonstration ne te dit pas, c'est à quelle distance peuvent être les premiers les uns des autres, ni à quelle taille peut atteindre le prochain premier après un quelconque. L'argument d'Euclide ne garantit que l'existence : quelque part au-delà de toute collection finie, un autre premier existe. La distribution des premiers le long de la droite numérique est une question bien plus difficile, et reste l'un des domaines les plus profonds et ouverts des mathématiques aujourd'hui.

Ce que la démonstration te dit, c'est structurel. Les nombres premiers ne peuvent pas être épuisés par des moyens finis. Tu pourrais consacrer une vie à les lister, et tu listerais toujours dans un reste infini. Chaque premier que tu trouves était réel, mais ceux qui t'attendaient devant l'étaient tout autant, tout aussi nombreux, et tout aussi inaccessibles par une liste finie.

Pour avoir une idée de la rapidité avec laquelle les nombres peuvent croître quand on les construit par multiplication et exposants, l'article sur la compréhension intuitive des exposants est un complément naturel : le produit p1 fois p2 fois ... fois pk croît plus vite qu'on ne l'attendrait, et cette croissance explique en partie pourquoi N finit par être si grand si rapidement.

Le zen de tout cela

La démonstration d'Euclide a plus de deux millénaires, et les mathématiciens ont trouvé des centaines de démonstrations du même résultat depuis. Aucune n'a rendu celle-ci obsolète. Elle conserve sa place non pas parce qu'elle est la plus ingénieuse ou la plus générale, mais parce qu'elle est la plus transparente.

Tu vois l'argument entier en une seule lecture. La construction est naturelle. La contradiction est nette. Il n'y a aucune étape où tu dois prendre quelque chose sur la foi ou faire confiance à une machine compliquée.

Ce que la démonstration te demande de garder à l'esprit est une seule idée : toute liste finie de premiers est déjà incomplète. Non pas parce que la liste est mal choisie, mais parce que les premiers sont le genre de chose qui ne peut pas être contenu par un décompte fini quelconque. Ils appartiennent à l'infini de la même façon que les entiers, ou les fractions, ou les points d'une droite. La démonstration ne te dit pas où se trouve le premier suivant. Elle te dit que le premier suivant est toujours là.

C'est suffisant. Cela a toujours été suffisant.

Pour d'autres résultats qui partagent cet esprit d'inévitabilité, le théorème de Goodstein montre une suite qui revient toujours à zéro malgré une croissance dépassant tout ce qui peut s'écrire, en utilisant la même logique de « quelque chose doit se passer parce que l'alternative est impossible ». Cette famille d'arguments vaut la peine d'être connue. Chacun est un angle différent sur le même fait fondamental : les mathématiques ne contiennent aucune échappatoire. La structure tient.