Des déserts de nombres premiers

Stratégie : construire, et non chercher. Plutôt que de partir à la recherche d'un long intervalle sans nombre premier, on en fabrique un, en imposant à chaque entier de la liste un diviseur qu'on aura choisi soi-même. La factorielle est l'outil exact pour cela : $n!$ est divisible par tous les entiers de $2$ à $n$ à la fois.

La démonstration. Soit $n\ge 2$ et soit $k$ un entier avec $2\le k\le n$. Comme $k$ figure parmi les facteurs du produit $n!=1\times 2\times \cdots \times n$, on a $k\mid n!$. Or $k$ divise aussi $k$. Le cours donne que si $k$ divise deux entiers, il divise leur somme :

$$k\mid n!+k.$$

Il reste à s'assurer que ce diviseur est strict, c'est-à-dire différent de $1$ et du nombre lui-même.

⚠️ C'est ici que se joue tout l'exercice. Un entier n'est pas composé parce qu'il admet un diviseur : $7$ admet le diviseur $7$. Il faut $1<k<n!+k$. La première inégalité vient de $k\ge 2$. La seconde vient de $n!>0$, et plus précisément de $n!\ge 2$ pour $n\ge 2$. Donc $n!+k$ possède un diviseur strictement compris entre $1$ et lui-même : il est composé.

Les $n-1$ entiers consécutifs

$$n!+2,n!+3,\dots ,n!+n$$

sont donc tous composés. Comme $n$ peut être choisi aussi grand qu'on veut, il existe des suites d'entiers consécutifs sans aucun nombre premier, de longueur arbitrairement grande.

Contrôle numérique. Prenons $n=5$, donc $5!=120$. Les quatre entiers annoncés sont $122$, $123$, $124$, $125$, et l'on retrouve bien les diviseurs prévus :

$$122=2\times 61,123=3\times 41,124=4\times 31,125=5\times 25.$$

Aucun n'est premier. ✔ Un test de primalité passé sur tous les $n!+k$ pour $n$ jusqu'à $9$ ne rencontre aucun nombre premier : la construction ne se trompe jamais.

Une remarque qui vaut la peine. La construction est très généreuse : pour obtenir un désert de quatre entiers, elle nous envoie autour de $120$, alors que le premier désert de quatre entiers commence en réalité dès $24,25,26,27$. Elle ne dit donc pas où sont les déserts, seulement qu'il en existe d'aussi longs qu'on veut.

Ce que l'exercice installe. Le contraste avec le théorème d'Euclide, qui affirme qu'il y a une infinité de nombres premiers. Les deux résultats coexistent sans se contredire : les nombres premiers ne s'arrêtent jamais, mais ils se raréfient, et l'on peut traverser des étendues arbitrairement longues sans en croiser un seul. C'est le premier aperçu de ce qu'on appellera plus tard la répartition des nombres premiers.