Il y en a toujours un de plus : la preuve d’Euclide, relue de près

Multipliez entre eux les premiers nombres premiers et ajoutez un. Deux fois trois plus un donne sept, qui est premier. Deux fois trois fois cinq plus un donne trente et un, premier lui aussi. On poursuit avec sept, puis avec onze : deux cent onze et deux mille trois cent onze sont encore premiers. L’élève qui a entendu raconter la preuve d’Euclide s’attend à ce que cela dure, puisqu’on lui a dit qu’Euclide « fabrique un nouveau nombre premier ». Avec treize, on obtient trente mille trente et un, qui vaut cinquante-neuf fois cinq cent neuf. La preuve d’Euclide n’est pas fausse pour autant. C’est le récit qu’on en fait qui l’est.

Cet article est le deuxième de la série Le peuple des nombres premiers, tirée de Mathématiques en terminales scientifiques (Tome 2). Il s’appuie sur le premier, « Un nombre premier n’est pas “un nombre qu’on ne peut pas décomposer” », paru le 7 octobre, dont il emploie la proposition 2 : tout entier au moins égal à deux possède un diviseur premier. Le blog a publié en 2021 une preuve topologique de l’infinité des nombres premiers, très éloignée de celle-ci ; l’article de la série à paraître le 23 octobre, « Fermat s’est trompé, et son erreur a produit un théorème », en donnera une troisième.

1. Le récit et le calcul

Notons p_{1}=2, p_{2}=3, p_{3}=5, et ainsi de suite, les nombres premiers rangés dans l’ordre croissant, et posons N_{k}=p_{1}p_{2}\cdots p_{k}+1. Les sept premières valeurs se calculent à la main.

\begin{array}{|c||l|} \hline p_{k} & N_{k}=p_{1}\cdots p_{k}+1 \\[0pt] \hline 2 & 3 \\ 3 & 7 \\ 5 & 31 \\ 7 & 211 \\ 11 & 2311 \\ 13 & 30031=59\times 509 \\ 17 & 510511=19\times 97\times 277 \\[0pt] \hline \end{array}

Les cinq premiers nombres N_{k} sont premiers, les deux suivants ne le sont pas. Un détail compte davantage que cet échec : les facteurs 59 et 509 ne figurent pas dans la liste 2, 3, 5, 7, 11, 13 qui a servi à fabriquer 30031. Le nombre construit n’est pas premier, mais ses facteurs premiers sont nouveaux. C’est cela, et cela seulement, que la démonstration garantit.

2. La démonstration du Tome 2

Théorème. L’ensemble des nombres premiers est infini.

Démonstration. Raisonnons par l’absurde, en supposant qu’il existe exactement m nombres premiers p_{1}, p_{2}, …, p_{m}, et posons

\displaystyle N=p_{1}\times p_{2}\times\cdots\times p_{m}+1.

Le nombre N est au moins égal à 3. D’après la proposition 2 du premier article de la série, il possède un diviseur premier, et ce diviseur figure dans la liste : c’est l’un des p_{k}. Le nombre p_{k} divise alors N et le produit p_{1}\cdots p_{m}, donc il divise leur différence, qui vaut 1. D’où p_{k}=1, ce qui contredit le fait qu’un nombre premier est au moins égal à 2. La supposition est fausse. \quad\Box

Relisez cette démonstration en y cherchant la phrase « N est premier ». Elle n’y est pas. Ce que l’on obtient, c’est un diviseur premier de N, et l’absurdité vient de ce que ce diviseur ne peut pas figurer dans la liste.

3. D’où vient le contresens ?

Il vient d’une autre rédaction de la même preuve, tout aussi correcte, que l’on rencontre souvent : « le nombre N n’est divisible par aucun des p_{k}, puisque la division laisse le reste 1 ; donc N est premier ; or N est plus grand que tous les p_{k} et ne figure pas dans la liste, ce qui est absurde ».

Dans ce texte, la phrase « N est premier » est légitime. Elle est déduite de l’hypothèse que les p_{k} sont tous les nombres premiers : si N n’était pas premier, son plus petit diviseur supérieur à 1 serait, d’après le premier article de la série, un nombre premier strictement inférieur à N, donc l’un des p_{k}, ce qui vient d’être exclu. Mais l’hypothèse est fausse — c’est tout l’objet du raisonnement —, et ce que l’on en a déduit tombe avec elle. L’élève retient l’étape intermédiaire comme un fait, alors qu’elle n’était qu’un pas vers la contradiction. Une phrase démontrée sous une hypothèse fausse n’est pas un théorème. Elle ne survit pas à la fin de la démonstration.

C’est la même famille d’erreur que celles qu’examinait l’article sur les règles de déduction : un énoncé sorti du contexte d’hypothèses dans lequel il avait été obtenu.

4. Euclide, lui, ne raisonne pas par l’absurde

La proposition 20 du livre IX des Éléments ne dit pas que l’ensemble des nombres premiers est infini. Elle dit que les nombres premiers sont plus nombreux que toute multitude proposée de nombres premiers. La différence n’est pas de style : Euclide ne suppose rien de faux, il prend une liste quelconque et en sort.

Sa démonstration prend trois nombres premiers A, B et C, forme le plus petit nombre qu’ils mesurent tous trois, et lui ajoute l’unité. Puis elle distingue deux cas. Ou bien le nombre obtenu est premier, et l’on a trouvé un nombre premier qui n’est ni A, ni B, ni C. Ou bien il ne l’est pas ; il est alors mesuré par un nombre premier G, et G n’est aucun des trois, sans quoi il mesurerait aussi l’unité. Un court raisonnement par l’absurde porte sur ce dernier point, mais l’ensemble de la preuve est direct.

Euclide envisage donc en toutes lettres que le nombre fabriqué ne soit pas premier. Le récit scolaire lui prête une erreur qu’il n’a pas commise.

La forme directe a un avantage sur la forme par l’absurde : elle fournit une méthode. Donnez-lui n’importe quelle liste finie de nombres premiers, elle rend un nombre premier qui n’y figure pas — le plus petit diviseur supérieur à 1 de N, dont le premier article de la série a établi qu’il est premier. Pour la liste 2, 3, 5, 7, 11, 13, elle rend 59.

5. Une majoration que la preuve contient

Cette méthode dit aussi où chercher le nombre premier suivant. Le résultat qui suit ne figure pas dans le Tome 2 ; il ne demande que la preuve d’Euclide et une récurrence.

Proposition. Pour tout entier n\geq 1, le n-ième nombre premier vérifie p_{n}\leq 2^{2^{n-1}}.

Démonstration. Pour n=1, on a p_{1}=2=2^{2^{0}}. Soit n\geq 1, et supposons l’inégalité vraie pour p_{1}, …, p_{n}. Le nombre N_{n}=p_{1}\cdots p_{n}+1 possède un diviseur premier q qui n’est aucun des p_{1}, …, p_{n} ; c’est donc un nombre premier au moins égal à p_{n+1}, et il ne dépasse pas N_{n}. Il en résulte

\displaystyle p_{n+1}\leq N_{n}\leq 2^{2^{0}+2^{1}+\cdots+2^{n-1}}+1=2^{2^{n}-1}+1\leq 2\times 2^{2^{n}-1}=2^{2^{n}}.\quad\Box

La borne est très mauvaise : elle donne p_{5}\leq 65536 pour un nombre qui vaut 11. Mais elle est explicite, et elle dit quelque chose que l’énoncé « l’ensemble est infini » tait : l’intervalle [1,\,2^{2^{n-1}}] contient au moins n nombres premiers.

Le même argument fonctionne avec la factorielle à la place du produit des premiers. Pour n\geq 1, aucun entier k compris entre 2 et n ne divise n!+1, puisque la division laisse le reste 1 ; tout diviseur premier de n!+1 est donc strictement supérieur à n. Là encore, le nombre fabriqué n’a aucune raison d’être premier : 4!+1=25=5^{2}, et 7!+1=5041=71^{2}. Ce sont ses facteurs qui sont nouveaux.

6. Ce que personne ne sait

Le contresens corrigé laisse une question légitime : les nombres N_{k} sont-ils premiers une infinité de fois ? On ne le sait pas. Les valeurs de k pour lesquelles N_{k} est premier ont été cherchées très loin par ordinateur, on en connaît une vingtaine, et aucune démonstration ne dit si la liste s’arrête. La preuve d’Euclide, qui tient en quatre lignes, porte ainsi sur des nombres dont on ignore presque tout. Elle n’en a pas besoin : elle n’utilise d’eux qu’une seule chose, le reste 1.

Le prochain article de la série, qui paraît le 11 octobre, passe de l’existence d’une infinité de nombres premiers à ce qu’ils permettent de faire de tout entier : le décomposer, et d’une seule façon.


Le théorème et sa démonstration par l’absurde sont ceux de la première section du chapitre 4, Nombres premiers, de Mathématiques en terminales scientifiques (Tome 2). Le texte d’Euclide, la majoration de la section 5 et la variante par la factorielle n’y figurent pas et sont construits ici.

3 réflexions sur “Il y en a toujours un de plus : la preuve d’Euclide, relue de près”

  1. Pingback: Fermat s’est trompé, et son erreur a produit un théorème | Formalis Mathematica

  2. Pingback: Une infinité de premiers congrus à 3 modulo 4 | Formalis Mathematica

  3. Pingback: Ce qu’on sait, ce qu’on croit, ce qu’on ignore | Formalis Mathematica

Votre commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.