L'infinité des premiers et leur répartition

Les nombres premiers s'espacent à mesure qu'on avance. S'arrêtent-ils un jour ? Euclide a répondu il y a plus de deux mille ans.

Il y en a une infinité

Théorème d'Euclide. L'ensemble des nombres premiers est infini.

La démonstration est l'une des plus élégantes des mathématiques. Elle procède par l'absurde :

1. Supposons qu'il n'y ait qu'un NOMBRE FINI de premiers : p1, p2, ..., pk.

2. Formons N = (p1 × p2 × ... × pk) + 1

3. N est plus grand que tous les pi, donc N n'est pas premier (par hypothèse).
   Il admet donc un diviseur premier p, qui figure dans notre liste.

4. Mais p divise le produit p1 × ... × pk, et p divise N.
   Donc p divise leur différence, qui vaut 1.

5. Aucun nombre premier ne divise 1.  CONTRADICTION.

L'hypothèse de départ est donc fausse : il y a une infinité de nombres premiers.

Une précision souvent mal comprise : N n'est pas nécessairement premier. Ainsi 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. La démonstration n'affirme pas que N est premier, mais que son diviseur premier échappe à la liste.

Ils se raréfient

intervalle          nombre de premiers
----------------    ------------------
1 à 100                    25
101 à 200                  21
1 001 à 1 100              16
10 001 à 10 100            11
1 000 001 à 1 000 100       6

Le théorème des nombres premiers, démontré en 1896, quantifie cette raréfaction :

                                n
   π(n)  ≈  ----------          où π(n) compte les premiers inférieurs à n
              ln(n)

n = 1 000       ->  estimation 145,     réel 168
n = 1 000 000   ->  estimation 72 382,  réel 78 498

L'approximation s'améliore relativement à mesure que n grandit. Concrètement : autour d'un nombre de 100 chiffres, environ un entier sur 230 est premier. C'est ce qui rend possible la génération de clés cryptographiques : on tire au hasard jusqu'à tomber sur un premier, et cela ne prend pas longtemps.

Une répartition irrégulière

Localement, rien n'est régulier. Les premiers jumeaux — deux premiers séparés de 2 — semblent ne jamais s'épuiser :

(3,5)  (5,7)  (11,13)  (17,19)  (29,31)  (41,43) ...

On en connaît d'énormes, mais personne n'a démontré qu'il y en a une infinité. C'est la conjecture des nombres premiers jumeaux, ouverte depuis plus d'un siècle. En 2013, Yitang Zhang a démontré qu'il existe une infinité de paires de premiers séparés d'au plus 70 millions ; l'effort collectif qui a suivi a fait descendre cette borne à 246 — encore loin de 2.

À l'inverse, on trouve des déserts arbitrairement longs : la suite

n! + 2,  n! + 3,  ...,  n! + n

fournit n - 1 entiers consécutifs tous composés, car n! + k est divisible par k. Il existe donc des intervalles d'un million d'entiers consécutifs sans aucun premier.

En résumé

• Euclide : il existe une infinité de nombres premiers, par l'absurde.
• Le nombre construit N = p1…pk + 1 n'est pas forcément premier — son diviseur échappe à la liste.
• Les premiers se raréfient : π(n) ≈ n / ln(n).
• Autour de 100 chiffres, environ 1 entier sur 230 est premier.
• Jumeaux : conjecture toujours ouverte ; la meilleure borne connue est 246.
• Il existe des déserts de longueur arbitraire, via n! + k.