On place $1$ au centre d'un quadrillage, $2$ à sa droite, puis on tourne dans le sens inverse des aiguilles d'une montre : $3$ au-dessus de $2$, $4$ et $5$ vers la gauche, $6$ et $7$ vers le bas, $8$, $9$ et $10$ vers la droite, et ainsi de suite. Voici le carré de $9$ cases de côté, avec les nombres premiers en foncé :

Déjà sur ce petit carré, on voit des premiers alignés en diagonale : $5$, $19$, $41$, $71$ vers le bas à gauche (en partant de $5$) ; $3$, $13$, $31$ vers le haut à droite ; $7$, $23$, $47$, $79$ vers le bas à droite. Sur un carré de $200$ cases de côté, ces alignements deviennent spectaculaires (voir la figure interactive).

Stanisław Ulam, photographie de son badge du laboratoire de Los Alamos pendant la guerre. Photo : Los Alamos National Laboratory, Wikimedia Commons, domaine public (gouvernement des États-Unis).

Stanisław Ulam (1909-1984) est né à Lwów, alors en Pologne (aujourd'hui Lviv, en Ukraine). Il quitte l'Europe en 1939 et rejoint pendant la guerre le laboratoire de Los Alamos, aux États-Unis, où il travaille à la bombe atomique, puis à la bombe H. Il y invente avec John von Neumann la méthode de Monte-Carlo, qui calcule par le hasard.

D'après le récit qu'en donne le journaliste scientifique Martin Gardner, Ulam assistait en 1963 à une réunion où il écoutait « un exposé long et très ennuyeux ». Pour passer le temps, il écrivit les entiers en spirale sur une feuille quadrillée et entoura les nombres premiers. Les diagonales le surprirent. De retour à Los Alamos, il fit tracer la spirale par l'ordinateur MANIAC II jusqu'à plusieurs dizaines de milliers, avec Myron Stein et Mark Wells ; ils publièrent leurs images en 1964. La même année, la spirale fit la couverture de la revue Scientific American (mars 1964), qui la rendit célèbre.

Le récit de la réunion vient de Gardner ; on ne connaît pas l'exposé en question. Gardner signale aussi qu'un herpétologue américain, Laurence Klauber, avait présenté dès 1932 un tableau triangulaire de nombres où les premiers s'alignaient également.

Suivons la diagonale qui part de $1$ vers le haut à droite : $1$, $3$, $13$, $31$, $57$, $91$… Notons $u_0 = 1$, $u_1 = 3$, $u_2 = 13$, etc. Calculons les écarts entre deux termes consécutifs, puis les écarts entre ces écarts :

Les écarts forment une suite arithmétique de raison $8$ : les « différences secondes » sont constantes. On va voir que c'est la signature d'un polynôme du second degré.

Appelons anneau numéro $k$ (pour $k \geqslant 1$) le bord du carré de côté $2k+1$ centré sur $1$. Le carré de côté $2k+1$ contient tous les nombres de $1$ à $(2k+1)^2$ : le dernier nombre écrit sur l'anneau $k$ est $(2k+1)^2$, situé dans le coin en bas à droite. Sur la grille ci-dessus, on lit bien $9$, $25$, $49$, $81$ dans ce coin.

L'anneau $k$ contient donc

nombres. On le parcourt en montant le long du côté droit, puis vers la gauche le long du côté haut, puis vers le bas le long du côté gauche, puis vers la droite le long du côté bas, chacun des trois derniers côtés comptant $2k$ pas. En remontant depuis le dernier nombre $(2k+1)^2$, on obtient les quatre coins :

• coin en bas à gauche : $(2k+1)^2 - 2k = 4k^2 + 2k + 1$ ;
• coin en haut à gauche : $(2k+1)^2 - 4k = 4k^2 + 1$ ;
• coin en haut à droite : $(2k+1)^2 - 6k = 4k^2 - 2k + 1$.

Vérification à la main. Pour $k = 2$ : $4 \times 4 + 4 + 1 = 21$, $4 \times 4 + 1 = 17$, $4 \times 4 - 4 + 1 = 13$. Ce sont bien les coins de l'anneau $2$ sur la grille. Les quatre demi-diagonales issues de $1$ sont donc décrites par quatre polynômes du second degré en $k$.

On peut aussi partir des écarts, comme dans le tableau. Pour la diagonale en haut à droite, $u_k = 4k^2 - 2k + 1$, donc

Inversement, si l'on sait seulement que $u_0 = 1$ et que $u_{k+1} - u_k = 8k + 2$, on retrouve $u_k$ en ajoutant les écarts :

en utilisant la somme $0 + 1 + \dots + (k-1) = \dfrac{(k-1)k}{2}$.

Propriété. Soit $P(k) = ak^2 + bk + c$ avec $a$, $b$, $c$ réels. Les écarts $d_k = P(k+1) - P(k)$ forment une suite arithmétique de raison $2a$.

Réciproquement, une suite dont les écarts forment une suite arithmétique est donnée par un polynôme du second degré (c'est le calcul de somme fait plus haut). Sur la spirale, les écarts croissent de $8$ à chaque anneau, parce que chaque anneau a $8$ nombres de plus que le précédent : toute ligne diagonale, même celles qui ne passent pas par $1$, est décrite par des polynômes de la forme $4k^2 + bk + c$. Les diagonales de la spirale sont des polynômes du second degré.

Sur la diagonale en haut à droite, les écarts $8k + 2$ sont tous pairs : tous les termes ont la même parité que $u_0 = 1$, ils sont tous impairs. Plus généralement, on peut montrer que chaque ligne diagonale ne contient que des nombres pairs, ou que des nombres impairs, et que ces lignes alternent : la diagonale qui passe par $4$ et $6$ ne contient que des pairs ($4$, $14$, $32$, $58$… et $6$, $20$, $42$, $72$…).

Comme tous les nombres premiers sauf $2$ sont impairs, une diagonale sur deux est vide de nombres premiers. C'est une première raison, très simple, pour laquelle l'œil voit des lignes. Nous verrons plus bas que ce n'est pas la seule.

En 1772, Leonhard Euler signale dans une lettre un polynôme remarquable : $E(n) = n^2 + n + 41$. Calculons ses premières valeurs.

Tous ces nombres sont premiers, et cela continue : $E(n)$ est premier pour tous les entiers $n$ de $0$ à $39$, soit quarante nombres premiers de suite (le dernier est $E(39) = 1\,601$). Le programme Python de la section sur le crible permet de le vérifier.

Pourquoi $n = 40$ échoue. On factorise : $E(40) = 40^2 + 40 + 41$ $= 40 \times 41 + 41$ $= 41 \times 41$. De même, $E(41) = 41^2 + 41 + 41 = 41 \times 43$. La série s'arrête donc forcément, et la raison est visible : le terme constant $41$ revient comme facteur.

Un nombre a d'autant plus de chances d'être premier qu'il évite les petits diviseurs $2$, $3$, $5$, $7$… Or $E(n)$ n'est jamais divisible par ces nombres-là. Montrons-le pour $2$, $3$ et $5$.

• Par $2$. $n^2 + n = n(n+1)$ est le produit de deux entiers consécutifs, dont l'un est pair : il est pair. Donc $E(n) = n(n+1) + 41$ est impair.
• Par $3$. On regarde le reste de $n$ dans la division par $3$. Si $n = 3q$ ou $n = 3q + 2$, l'un des deux facteurs $n$ ou $n+1$ est multiple de $3$, donc $n(n+1)$ aussi ; comme $41 = 3 \times 13 + 2$, $E(n)$ a pour reste $2$. Si $n = 3q + 1$, alors $n(n+1) = (3q+1)(3q+2)$ $= 9q^2 + 9q + 2$, donc $E(n) = 9q^2 + 9q + 43$, de reste $1$ car $43 = 3 \times 14 + 1$. Le reste n'est jamais nul.
• Par $5$. Le même raisonnement, avec les cinq restes possibles de $n$, montre que $n(n+1)$ a pour reste $0$, $2$, $1$, $2$ ou $0$ : comme $41$ a pour reste $1$, $E(n)$ a pour reste $1$, $3$, $2$, $3$ ou $1$, jamais $0$.

Le même calcul fonctionne pour tous les nombres premiers inférieurs à $41$ : aucun ne divise jamais $E(n)$. C'est ce qui rend ce polynôme si riche en nombres premiers. Parmi les $1\,000$ premières valeurs $E(0)$, …, $E(999)$, on compte $581$ nombres premiers, alors que ces valeurs atteignent le million ; pour des entiers de cette taille pris au hasard, on n'en attendrait qu'environ $7\,\%$ (voir plus bas).

Le mathématicien allemand Georg Rabinowitsch a montré en 1913 que les seuls nombres $p$ pour lesquels $n^2 + n + p$ est premier pour tout $n$ de $0$ à $p - 2$ sont $2$, $3$, $5$, $11$, $17$ et $41$. On les appelle parfois les « nombres chanceux d'Euler » ; la démonstration dépasse largement le lycée.

Commençons la spirale à $41$ au lieu de $1$ : chaque case contient alors son ancien nombre augmenté de $40$. D'après les formules des coins :

• vers le bas à gauche, on lit $4k^2 + 2k + 41$ $= (2k)^2 + 2k + 41$ $= E(2k)$ ;
• vers le haut à droite, on lit $4k^2 - 2k + 41$ $= (2k-1)^2 + (2k-1) + 41$ $= E(2k-1)$.

(Pour la seconde égalité, on développe $(2k-1)^2 + (2k-1)$ $= 4k^2 - 4k + 1 + 2k - 1$ $= 4k^2 - 2k$.) Les deux demi-diagonales forment une seule ligne, qui contient toutes les valeurs $E(0)$, $E(1)$, $E(2)$… : sur la spirale qui commence à $41$, quarante nombres premiers consécutifs sont alignés sur la diagonale. La figure interactive permet de le voir.

Sur la spirale, les points sont de plus en plus clairsemés en s'éloignant du centre : les nombres premiers se raréfient. Mais ils ne s'arrêtent jamais.

Propriété (Euclide, vers 300 avant notre ère). Il existe une infinité de nombres premiers.

Entre deux nombres premiers, l'écart peut être immense. Prenons un entier $n \geqslant 2$ et regardons les $n - 1$ entiers consécutifs

Pour tout $j$ compris entre $2$ et $n$, $j$ divise $n!$ (c'est l'un des facteurs de $1 \times 2 \times \dots \times n$) et $j$ divise $j$, donc $j$ divise $n! + j$, qui n'est pas premier. À la main, pour $n = 5$ : $5! = 120$, et $122$, $123$, $124$, $125$ sont divisibles respectivement par $2$, $3$, $4$ et $5$. Avec $n = 1\,000$, on obtient $999$ entiers consécutifs sans aucun nombre premier.

On note $\pi(x)$ le nombre de nombres premiers inférieurs ou égaux à $x$ (la lettre $\pi$ n'a ici aucun rapport avec le nombre $3{,}14\dots$). Par exemple, $\pi(10) = 4$ (ce sont $2$, $3$, $5$, $7$). Vers 1792, le jeune Carl Friedrich Gauss, en étudiant des tables, remarque que $\pi(x)$ est proche de $\dfrac{x}{\ln x}$ ; Adrien-Marie Legendre propose en 1798 une approximation voisine.

Le rapport diminue lentement vers $1$. C'est le théorème des nombres premiers, démontré en 1896, indépendamment, par Jacques Hadamard et Charles de la Vallée Poussin :

Attention : cela ne veut pas dire que la différence $\pi(x) - \dfrac{x}{\ln x}$ tend vers $0$ ; elle grandit au contraire (environ $6\,100$ pour un million), mais elle devient petite par rapport à $\pi(x)$.

La proportion de nombres premiers parmi les entiers de $1$ à $x$ vaut $\dfrac{\pi(x)}{x}$. D'après le théorème, elle est proche de $\dfrac{1}{\ln x}$, qui tend vers $0$ puisque $\ln x$ tend vers $+\infty$. À la main : vers $100$, environ un nombre sur $\ln 100 \approx 4{,}6$ est premier ; vers un million, un sur $\ln 10^6 \approx 13{,}8$ ; vers un milliard, un sur $20{,}7$. La raréfaction est donc très lente : il faut multiplier $x$ par environ $2{,}7$ (le nombre $e$) pour que $\ln x$ augmente de $1$.

On en tire une règle approchée utile : « un entier pris au hasard près de $x$ est premier avec une probabilité d'environ $\dfrac{1}{\ln x}$ ». C'est cette règle qui permet de comparer le polynôme d'Euler au hasard : près d'un million, on attendrait environ $7\,\%$ de premiers, et $E(n)$ en donne beaucoup plus.

Le savant grec Ératosthène (IIIe siècle avant notre ère) a donné une méthode pour trouver tous les premiers jusqu'à un entier $N$ : on écrit les entiers de $2$ à $N$ ; le premier non barré, $2$, est premier, et on barre tous ses multiples $4$, $6$, $8$… ; le suivant non barré, $3$, est premier, on barre $6$, $9$, $12$… ; puis $5$, puis $7$.

Pour $N = 50$, on peut s'arrêter après $7$ : tout ce qui reste est premier. On trouve $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$ et $47$, soit $\pi(50) = 15$.

Pourquoi s'arrêter à $\sqrt{N}$ ? Si un entier $m \leqslant N$ n'est pas premier, il s'écrit $m = ab$ avec $2 \leqslant a \leqslant b$. Alors $a^2 \leqslant ab = m \leqslant N$, donc $a \leqslant \sqrt{N}$ : $m$ a un diviseur au plus égal à $\sqrt{N}$, et il a déjà été barré. Comme $\sqrt{50} \approx 7{,}07$, les nombres $2$, $3$, $5$ et $7$ suffisent.

Le programme suivant construit le crible, compte les premiers jusqu'à $x$ et compare à $\dfrac{x}{\ln x}$, puis teste le polynôme d'Euler. On peut le modifier et l'exécuter.

Le point de vue de l'informatique. Tester un nombre de $n$ chiffres en divisant jusqu'à sa racine demande de l'ordre de $10^{n/2}$ divisions : impossible pour les nombres de plusieurs centaines de chiffres qu'utilise la cryptographie (voir le texte en préparation sur la cryptographie). Les ordinateurs utilisent d'autres tests, fondés sur des propriétés des restes, qui décident en quelques instants si un nombre est premier.