Peut-on finir la liste des nombres premiers ?

Les nombres premiers commencent par $2,3,5,7,11,13,\ldots$ On peut en chercher toujours plus, mais trouver beaucoup de nombres premiers ne suffit pas à prouver que la liste ne s'arrêtera jamais. Dans ce problème, on va partir d'un calcul avec $2$, $3$ et $5$, puis faire peu à peu disparaître les nombres eux-mêmes pour comprendre ce qui se passe avec une liste finie quelconque.

I - Tout entier supérieur à 1 rencontre un nombre premier

On rappelle qu'un nombre premier est un entier supérieur à $1$ qui possède exactement deux diviseurs positifs : $1$ et lui-même.

1. Soit $N$ un entier strictement supérieur à $1$. Le nombre $N$ est lui-même un diviseur de $N$, puisque $N=N\times1$. Il existe donc au moins un diviseur de $N$ strictement supérieur à $1$. Tous ces diviseurs sont parmi les entiers $2,3,\ldots,N$ ; comme il n'y a qu'un nombre fini de tels entiers, l'un de ces diviseurs est nécessairement le plus petit. On l'appelle $d$. Montrer que $d$ est nécessairement premier.

Indice : que se passerait-il si $d$ n'était pas premier ? Un diviseur de $d$ serait-il aussi un diviseur de $N$ ?

Vous venez d'établir un résultat que nous utiliserons dans tout le problème : tout entier strictement supérieur à $1$ possède au moins un diviseur premier. Remarquez déjà la forme du raisonnement : on peut envisager qu'une affirmation soit vraie, puis découvrir que cette hypothèse conduit à une impossibilité.

II - Et s'il n'existait que 2, 3 et 5 ?

Imaginons provisoirement un monde dans lequel les seuls nombres premiers seraient $2$, $3$ et $5$. Il ne s'agit pas d'affirmer que ce monde existe : nous allons simplement examiner jusqu'où cette hypothèse nous conduit.

2. On construit

$$A=2\times3\times5+1=31.$$

Sans effectuer trois divisions posées, expliquer pourquoi aucun des nombres $2$, $3$ et $5$ ne divise $31$.

3. D'après la partie I, $31$ possède au moins un diviseur premier. Dans le monde imaginé ci-dessus, quelles seraient les seules possibilités pour ce diviseur premier ? Comparer avec la question 2 et expliquer précisément ce qui devient impossible. Quelle conclusion peut-on tirer sur l'hypothèse de départ ?

Le raisonnement que vous venez d'utiliser porte un nom : le raisonnement par l'absurde. On imagine provisoirement un « autre monde » dans lequel une affirmation serait vraie, puis on suit honnêtement les conséquences de cette hypothèse. Si ce monde conduit à deux conclusions incompatibles, il ne peut pas être cohérent : l'affirmation de départ ne pouvait donc pas être vraie. Ici, nous avons seulement montré que $2$, $3$ et $5$ ne peuvent pas constituer la liste complète des nombres premiers. Cela ne prouve pas encore qu'il y en a une infinité.

III - Le piège de 31

Le nombre $31$ est lui-même premier. Ce hasard peut donner une fausse idée : peut-être que le produit de plusieurs nombres premiers, augmenté de $1$, est toujours premier. L'exemple suivant montre que ce n'est pas vrai :

$$2\times3\times5\times7\times11\times13+1 =30031 =59\times509.$$

4. Le nombre $30031$ est donc composé. Dans les questions suivantes, on n'utilisera pas les nombres $59$ et $509$ eux-mêmes.

(a) Expliquer pourquoi aucun des nombres premiers

$$2,\ 3,\ 5,\ 7,\ 11,\ 13$$

ne divise $30031$.

Indice : quel est le reste de la division de $30031$ par chacun de ces nombres ?

(b) D'après la partie I, $30031$ possède au moins un diviseur premier ; appelons-le $q$. Imaginons un instant que $q$ soit l'un des six nombres premiers de la liste ci-dessus. Quelle contradiction obtient-on avec la question (a) ? Que peut-on en conclure sur $q$ ?

(c) Formuler, en une ou deux phrases, ce qui est réellement important dans la construction « produit de la liste $+1$ ».

Le nombre construit n'a donc pas besoin d'être premier. Ce qui compte est qu'il possède un diviseur premier nouveau, c'est-à-dire absent de la liste de départ.

IV - Allonger la liste sans changer l'idée

5. Une feuille contient d'abord quatre nombres premiers. On multiplie tous les nombres écrits sur la feuille, puis on ajoute $1$ au produit obtenu.

Expliquer, sans connaître les valeurs de ces quatre nombres, pourquoi la division du nouvel entier par n'importe quel nombre premier écrit sur la feuille laisse un reste égal à $1$.

Supposons maintenant que la feuille contienne dix nombres premiers, puis cent nombres premiers. Qu'est-ce qui change dans le raisonnement précédent ? Formuler finalement une phrase qui soit valable pour n'importe quelle liste finie de nombres premiers.

À ce stade, la longueur exacte de la liste n'a plus d'importance : quatre, cent ou beaucoup plus, le même raisonnement fonctionne tant que la liste est finie.

V - Que signifie vraiment « il n'y en a qu'un nombre fini » ?

6. Emma affirme : « Il n'existe qu'un nombre fini de nombres premiers, mais ils sont peut-être tellement nombreux qu'on ne pourrait jamais tous les écrire. » Expliquer pourquoi, si cette affirmation était vraie, il existerait tout de même en principe une liste finie contenant absolument tous les nombres premiers.

7. Admettons provisoirement qu'une liste finie contenant tous les nombres premiers existe. À l'aide des idées construites dans les parties précédentes, que peut-on construire à partir de cette liste pour mettre à l'épreuve son caractère complet ? Mener le raisonnement jusqu'à une contradiction.

Votre raisonnement devra expliquer pourquoi aucun nombre premier de la liste ne divise l'entier construit, pourquoi cet entier possède pourtant un diviseur premier, puis pourquoi ces deux faits sont incompatibles avec le caractère complet de la liste.

La contradiction porte maintenant sur une liste finie supposée contenir tous les nombres premiers. Nous ne réfutons plus une liste particulière comme $2,3,5$ : nous montrons qu'aucune liste finie ne peut être complète.

VI - Comprendre et rédiger la preuve

8. Dans le raisonnement de la question 7, identifier clairement : l'hypothèse que l'on a supposée vraie, les deux conclusions qui deviennent incompatibles, puis ce que cette contradiction permet de conclure. Expliquer en particulier pourquoi une contradiction ne signifie pas que « le calcul a raté ».

9. Rédiger maintenant une démonstration complète et autonome de l'infinité des nombres premiers, essentiellement en français, sans renvoyer aux questions précédentes. Vous pouvez commencer par :

« Supposons qu'il n'existe qu'un nombre fini de nombres premiers. On pourrait alors tous les écrire dans une liste... »

Pour aller plus loin - facultatif

10. On suppose à nouveau qu'il n'existe qu'un nombre fini de nombres premiers et on les note $p_1,p_2,\ldots,p_r$. En posant

$$N=p_1p_2\cdots p_r+1,$$

réécrire la démonstration précédente sous une forme plus compacte.

Vous êtes partis d'un calcul avec $2$, $3$ et $5$. À la fin, les valeurs particulières ont disparu : l'idée essentielle est qu'une liste finie, quelle que soit sa longueur, permet toujours de construire un entier qui force l'apparition d'un nombre premier absent de cette liste. Cette idée remonte aux Éléments d'Euclide ; le corrigé revient sur la différence entre sa présentation antique et la reformulation moderne utilisée aujourd'hui.