Les nombres premiers

Histoire

.            Presque tous les nombres peuvent se décomposer en un produit de nombres entiers plus petits :

4  (2 × 2),          6  (2 × 3),         8  (2 × 2 × 2),            9  (3 × 3),         etc.

Ceux qui ne le peuvent pas sont appelés « nombres premiers ». C’est le cas de 2, 3, 5, 7, 11, 13, 17, etc. Un nombre entier est premier s’il n’admet que deux diviseurs distincts entiers et positifs (1 et lui-même). Ainsi 1 n’est pas premier car il n’a qu’un seul diviseur entier positif ; 0 non plus, car il est divisible par tous les entiers positifs.

À l’exception de 2 et 5, les nombres premiers ne peuvent se terminer par les chiffres 0, 2, 4, 6, 8 et 5 (sans quoi ils sont divisibles par 2 ou 5). Les nombres premiers se terminent donc par 1, 3, 7 ou 9.

.            Les nombres premiers sont les briques élémentaires de l’arithmétique, c’est-à-dire la moitié des mathématiques. Il y a 2.300 ans, Euclide a démontré qu’il existait une infinité de ces « briques élémentaires » de l’arithmétique. Cela veut dire que l’on pourra toujours trouver de nouveaux nombres premiers. La seule limite réside aujourd’hui dans la puissance de calcul des ordinateurs.

.            Des nombres particuliers ont été « inventés » au début du XVIIe siècle par un moine français, Marin Mersenne. Ils sont formés en multipliant le chiffre 2 par lui-même un certain nombre de fois, puis en retranchant 1 au résultat. On les note ainsi (2n - 1). Il se trouve que lorsque le nombre n’est pas premier, le nombre de Mersenne associé est, de temps en temps, premier lui aussi.

.            En 2013, le plus grand nombre premier connu faisait plus de 17 millions de chiffres. Il aura fallu près de deux ans pour le détrôner. Début janvier 2016, Dr Curtis Cooper, professeur à l’University of Central Missouri a calculé un nouveau mastodonte de 22 millions de chiffres. Si on l’imprimait de telle façon que chaque chiffre qui le compose fasse un millimètre de large, l’ensemble ferait 22 km de long !

En janvier 2016, c’est en multipliant 74 207 281 fois le chiffre deux par lui-même que l’on a obtenu l’antépénultième né :     274 207 281 -  1.

Le 26 décembre 2017, J. Pace, G. Woltman, S. Kurowski, A. Blosser, du Great Internet Mersenne Prime Search (GIMPS) annoncent la découverte d’un nouveau nombre premier : 277 232 917 - 1. C'est le 50e nombre de Mersenne, qui comporte 23 249 425 chiffres, écrit en base 10, soit près d'un million de chiffres supplémentaires par rapport à l'ancien record (janvier 2016). Un document word écrit en Times New Roman, avec une taille de police de 10 et les marges classiques, représenterait 3.845 pages.

Le 7 décembre 2018, un record été battu, celui du plus grand nombre premier connu, 282 589 933 − 1, qui comporte près de 25 millions de chiffres en écriture décimale. On doit cette performance (la vérification est en cours) au GIMPS. Grâce à l’algorithmique de Lucas, 39 jours de calcul ont suffi à l’ordinateur de l’université américaine pour vérifier la primalité du nouveau recordman du monde.

Depuis 1996, 15 nombres premiers, les plus longs connus à ce jour, ont ainsi été découverts.

Quelques exemples de décompositions en produit de facteurs premiers

.            N’importe quel nombre s’écrit comme un produit de nombres premiers. Par exemple : 132 = 2 × 2 × 3 × 11. De plus, cette décomposition est unique. C’est ce que l’on appelle le théorème fondamental de l’arithmétique qui était déjà connu en Grèce antique.

1 111 111 = 239 x 4 649

100 = 2 x 2 x 5 x 5

123 456 789 = 3 x 3 x 3.803 x 3.607

1 024 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 210

65 000 = 2 x 2 x 2 x 5 x 5 x 5 x 5 x 13 = 23 x 54 x 13

1 515 151 515 151 515 = 3 x 5 x 17 x 73 x 101 x 137 x 5 882 353

23 571 113 171 923 293 137 = 7 x 672 x 151 x 4 967 701 595 369

1 000 000 000 000 000 000 000 001 = 17 x 9 999 999 900 000 001 x 5 882 353

La conjecture de Goldbach

.            Tout nombre entier plus grand que 2 s’écrit comme somme d’au plus trois nombres premiers. Par exemple :  622 = 23 + 599, et 23 comme 599 sont des nombres premiers.

Le crible d’Ératosthène

.            On ne connaît aucune propriété simple (autre que celle qui les définit) que satisferaient les nombres premiers. En dehors de ne pas être divisibles, les nombres premiers semblent avoir un comportement complètement chaotique.

Le crible d’Ératosthène consiste à écrire tous les nombres d’un intervalle donné, puis à éliminer méthodiquement les multiples des nombres premiers successifs déjà connus, en s’arrêtant à la racine carrée de la borne supérieure de l’intervalle. Les nombres restants sont les nombres premiers de l’intervalle.

Il y a 78 948 nombres premiers plus petits que 1 000 000.

On a récemment utilisé le crible d’Eratosthène pour étudier les écarts entre les nombres premiers. À cette occasion, on a appliqué le crible par tranches de 1010 : après avoir sauvé les informations désirées, on effaçait les résultats du calcul de chacune de 100.000 tranches (sauf la première) afin de traiter la suivante.

Si, au lieu de les effacer, on avait sauvé à chaque fois les résultats intermédiaires, on aurait disposé de la table des 29 844 570 422 669 nombres premiers inférieurs à 1015. Le stockage de cette table aurait nécessité une mémoire de 20.1010 octets, soit plus de 30.000 CD-ROM de 650 mégaoctets chacun, ou plus de 1.000 DVD double face double couche de 17 gigaoctets chacun (ce sont les DVD de plus grande capacité aujourd’hui). Il est clair que pour connaître des nombres premiers de 20 chiffres ou plus ou pour factoriser des entiers de cette taille, le crible d’Ératosthène ne convient pas.

Constituer de très grandes tables de nombres premiers est impossible — à cause de la mémoire nécessaire — et inutile, car on dispose d’autres méthodes pour connaître la primalité : il vaut mieux recalculer que stocker. Aujourd’hui, on sait tester si un nombre entier quelconque de 100 chiffres est premier, alors qu’un ordinateur de la taille du Système solaire ne suffirait pas à stocker la table de tous les nombres premiers inférieurs à 10100.

Distribution des nombres premiers

.            Il n’existe pas de formule simple qui puisse fournir le n-ième nombre premier. Au même moment (1896), mais indépendamment, Jacques Hadamard et Charles-Jean de la Vallée-Poussin ont montré que cette distribution suit une courbe logarithmique, qui tend donc vers l’infini (pn n log(n), le n-ième nombre premier, est du même ordre de grandeur que n log(n)). Ce théorème des nombres premiers ne donne pas de formule pour le nieme nombre premier mais donne son comportement « à l’infini ». On peut voir ce résultat comme analogue au fait que l’on est incapable de prévoir le résultat d’un lancer de dé mais dont on sait que lorsque le nombre de lancers augmente la proportion d’une face obtenue quelconque tend vers 1/6.

Le théorème de la raréfaction des nombres premiers (1808) montre qu’à l’infini, la densité des nombres premiers est nulle, et donc qu’ils sont de plus en plus rares !

Nombres premiers jumeaux

.            En mathématiques, deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de deux.

Nombres premiers jumeaux jusqu'à 1000 :

(3, 5) (5, 7) (11, 13) (17, 19) (29, 31) (41, 43) (59, 61) (71, 73) (101, 103) (107, 109) (137, 139) (149, 151) (179, 181) (191, 193) (197, 199) (227, 229) (239, 241) (269, 271) (281, 283) (311,313) (347, 349) (419, 421) (431, 433) (461, 463) (521, 523) (569, 571) (599, 601) (617,619) (641, 643) (659, 661) (809, 811) (821, 823) (827, 829) (857, 859) (881, 883)

Il y a 8 169 paires de nombres premiers jumeaux plus petits que 1 000 000.

En vertu du  théorème de la raréfaction des nombres premiers, on constate que leur densité diminue, allant de 75% pour les nombres premiers inférieurs à 10,  61,5% pour les nombres premiers inférieurs à 100, jusquà environ 15 % pour 108 (100 000 000), …

Quelques propriétés :

.            Le couple (2, 3) est le seul couple de nombres premiers consécutifs.

En omettant le couple (2, 3), 2 est la plus petite distance possible entre deux nombres premiers ; deux nombres premiers jumeaux sont ainsi deux nombres impairs consécutifs.

Tout couple de nombres premiers jumeaux (à l'exception du couple (3, 5)) est de la forme (6n – 1, 6n + 1) pour un certain entier naturel n. En effet, toute série de trois entiers naturels consécutifs comporte au moins un multiple de 2 (éventuellement deux) et un seul multiple de 3 ; l'entier qui se trouve entre les deux nombres premiers jumeaux est à la fois ce multiple de 2 et ce multiple de 3, car cela ne peut pas être l'un des nombres premiers.

Alors que la série des inverses des nombres premiers est divergente, la série des inverses de nombres premiers jumeaux est convergente (vers un nombre appelé constante de Brun = ~ 1,902).

La conjecture des nombres premiers jumeaux affirme qu'il existe une infinité de nombres premiers jumeaux.

Nombres premiers cousins

.            Deux nombres premiers cousins sont deux nombres premiers qui diffèrent de quatre.

Exemple : 193 est un nombre premier jumeau avec 191 et un nombre premier cousin avec 197. Les nombres premiers cousins inférieurs à 1 000 sont :

(3, 7) (7, 11) (13, 17) (19, 23) (37, 41) (43, 47) (67, 71) (79, 83) (97, 101) (103, 107) (109,113) (127, 131) (163, 167) (193, 197) (223, 227) (229, 233) (277, 281) (307, 311) (313,317) (349, 353) (379, 383) (397, 401) (439, 443) (457, 461) (487, 491) (499, 503) (613, 617) (643, 647) (673, 677) (739, 743) (757, 761) (769, 773) (823, 827) (853, 857) (859, 863) (877, 881) (883, 887) (907, 911) (937, 941) (967, 971)

Il découle de la première conjecture de Hardy-Littlewood que les nombres premiers cousins ont la même densité asymptotique que les nombres premiers jumeaux.

Nombres premiers sexy

.            Deux nombres premiers sexy sont deux nombres premiers qui diffèrent de six. Le terme «sexy» est un jeu de mot basé sur le mot latin pour « six » : sex.

Les couples de nombres premiers sexy inférieurs à 500 sont :

(5,11) (7,13) (11,17) (13,19) (17,23) (23,29) (31,37) (37,43) (41,47) (47,53) (53,59) (61,67) (67,73) (73,79) (83,89) (97,103) (101,107) (103,109) (107,113) (131,137) (151,157) (157,163) (167,173) (173,179) (191,197) (193,199) (223,229) (227,233) (233,239) (251,257) (257,263) (263,269) (271,277) (277,283) (307,313) (311,317) (331,337) (347,353) (353,359) (367,373) (373,379) (383,389) (433,439) (443,449) (457,463) (461,467)

En novembre 2005, le plus grand couple de nombre premiers sexy connu était (p, p+6) pour

p = (48011837012 × ((53238 × 7879#)² - 1) + 2310) × 53238 × 7879# / 385 + 1,

où 7879# est une primorielle. Il est composé de 10 154 chiffres.

Comme pour les nombres premiers jumeaux, il en existe probablement une infinité mais cela n'est pas démontré.

Primorielle

.            Notée n# ou P(n), pour un nombre entier n, c’est le produit de tous les nombres premiers inférieurs ou égaux à n.

Par exemple, P(7) = 2 × 3 × 5 × 7 = 210 est une primorielle.

  p                                 P(p)

  2                                     2

  3                                     6

  5                                   30

  7                                 210

11                              2 310

13                            30 030

17                          510 510

19                       9 699 690

23                   223 092 870

29                6 469 693 230

31             200 560 490 130

37          7 420 738 134 810

Triplets

.            Comme les nombres premiers jumeaux, les nombres premiers sexy peuvent être étendus à des constellations plus grandes.

Ce sont les triplets de nombres premiers sexys de la forme (p, p+6, p+12).

Les triplets inférieurs à 1 000 sont :

(7,13,19) (17, 23, 29) (31, 37, 43) (47, 53, 59) (67, 73, 79) (97, 103, 109) (101, 107, 113) (151,157, 163) (167, 173, 179) (227, 233, 239) (257, 263, 269) (271, 277, 283) (347, 353, 359) (367, 373, 379) (557, 563, 569) (587, 593, 599) (607, 613, 619) (647, 653, 659) (727, 733, 739) (941, 947, 953) (971, 977, 983)

En avril 2006, le plus grand triplet de nombres premiers sexy connu était (p, p+6, p+12) pour :

p = (84055657369 × 205881 × 4001# × (205881 × 4001# + 1) + 210) × (205881 × 4001# - 1) / 35 + 1.

Il comporte 5 132 chiffres.

Quadruplets

.            De façon similaire, on peut définir des quadruplets de nombres premiers sexys (p, p+6, p+12, p+18). À l'exception du quadruplet (5, 11, 17, 23), la représentation décimale de p finit forcément par « 1 ».

Les quadruplets inférieurs à 1 000 sont :

(5, 11, 17, 23) (11, 17, 23, 29) (41, 47, 53, 59) (61, 67, 73, 79) (251, 257, 263, 269) (601,607, 613, 619) (641, 647, 653, 659)

En novembre 2005, le plus grand quadruplet de nombres premiers sexy connu était (p, p+6, p+12, p+18) pour :

p = 411784973 × 2347# + 3301

Il comporte 1 002 chiffres.

Quintuplets

.            Comme chaque sixième nombre de la forme 6n - 1 est divisible par 5, le seul quintuplet de nombres premiers sexy existant est (5,11,17,23,29), et il n'est pas possible de trouver une séquence plus longue (sextuplet, etc.).

Nombre premier de Sophie Germain

.            Un nombre premier « p » est appelé nombre premier de Sophie Germain, noté « G » dans cet article, si « 2p + 1 » est aussi un nombre premier. Le nombre premier résultant (« 2G + 1 »), noté « S », est alors appelé nombre premier sûr.

Ces nombres premiers particuliers ont reçu une signification en raison de la démonstration de Sophie Germain à propos de la véracité du dernier théorème de Fermat pour de tels nombres premiers.

Il est conjecturé qu'il existe une infinité de nombres premiers de Sophie Germain ; cependant, comme pour la conjecture des nombres premiers jumeaux, ceci n'a pour le moment pas été démontré.

Les premiers nombres premiers de Sophie Germain sont :

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1 013, 1 019, 1 031, 1 049, 1 103, 1 223, 1 229, 1 289, ...

Les nombres premiers palindromes

.            Un nombre (mot, Georges Pérec a composé un texte de 1.247 mots palindromes!) palindrome se lit de droite à gauche et de gauche à droite. Tout entier est la somme de 3 palindromes au plus.

Le nombre 11 est le seul nombre palindrome à deux chiffres qui soit premier : en effet, un tel nombre est de la forme XX, donc multiple de 11. Plus généralement, à l’exception de 11, il n’existe aucun nombre premier palindrome ayant un nombre pair de chiffres.

En revanche, il existe 15 nombres premiers palindromes à trois chiffres :

101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929.

Notez qu’aucun n’a pour chiffre des centaines 2, 4, 5, 6 et 8.

Il existe 93 nombres premiers palindromes à cinq chiffres, et 668 à sept chiffres. Parmi ces derniers, mentionnons le quadruplet suivant (chiffre central en gras) :

1878781 — 1879781 — 1880881 — 1881881

Cette suite est remarquable, car elle est composée de quatre nombres premiers palindromes pris dans quatre groupes consécutifs de 1 000 (c’est l’unique cas de ce type). Tous les nombres premiers palindromes de 11, 13 et 15 chiffres ont été calculés par Martin Eibl. Le 9 juin 1998, ceux à 17 chiffres ont été calculés par Carlos Rivera. Ce Mexicain, passionné de nombres premiers, n’est pas un chercheur : il travaille dans l’industrie des céramiques à Monterrey, mais il a trouvé le temps de mettre en place un site Internet où il présente toutes sortes de propriétés et d’énigmes récréatives concernant les nombres premiers palindromes.

Voici quelques-unes des identités amusantes notées par Rivera.

Entre nombres premiers palindromes à trois chiffres :

101 + 131 + 151 = 383

Du même type, avec des palindromes premiers à cinq chiffres :

30103 + 30203 + 30403 = 90709

Plus impressionnante, entre palindromes premiers à 43 chiffres :

+   1000000000000002109952599012000000000000001

+   1000000000000002110000000112000000000000001

+   1000000000000002110025200112000000000000001

=   3000000000000006329977799236000000000000003

Cette égalité est la plus petite possible de sa catégorie (une somme de trois nombres premiers palindromes de 43 chiffres donnant un nombre premier palindrome de 43 chiffres). Toutefois, ce n’est qu’une égalité simple à côté de la suivante, où l’on a utilisé la notation (0)n pour désigner une suite de n zéros consécutifs. Il s’agit cette fois d’une égalité entre nombres premiers palindromes de 191 chiffres (notez que 191 est aussi un nombre premier palindrome) :

+   1 (0)87 132298010892231 (0)87 1

+   1 (0)87 132300858003231 (0)87 1

+   1 (0)87 132301111103231 (0)87 1

=   3 (0)87 396899979998693 (0)87 3

Toujours plus fort (ou plus absurde, selon les goûts), Rivera a découvert que le nombre premier palindrome 71317 s’écrit de trois façons différentes comme somme de nombres premiers consécutifs :

71317 = 2351 + 2357 + ... + 2579 + 2591 (29 nombres premiers consécutifs)

71317 = 10163 + 10169 + 10177 + 10181 + 10193 + 10211 + 10223 (sept nombres premiers consécutifs)

71317 = 14243 + 14249 + 14251 + 14281 + 14293 (cinq nombres premiers consécutifs)

Parmi les identités farfelues, les suivantes, découvertes au sujet du nombre premier palindrome 134757431, semblent miraculeuses. Ce nombre, qui mérite peut-être le titre de « nombre premier palindrome le plus intéressant », peut s’écrire de trois façons différentes comme somme de puissances des nombres 1, 2, 3, 4, 5, 6, 7, 8, 9, chacun pris une seule fois :

134757431 = 17 + 23 + 38 + 45 + 54 + 62 + 71 + 89 + 96

134757431 = 17 + 25 + 38 + 41 + 52 + 64 + 73 + 89 + 96

134757431 = 17 + 28 + 34 + 42 + 53 + 65 + 71 + 89 + 96

C’est le seul nombre qui possèderait cette propriété. Il existerait - paraît-il - un autre nombre premier palindrome qu’on peut exprimer de deux façons différentes comme somme de puissances des nombres 1, 2, 3, 4, 5, 6, 7, 8, 9.