Nombre de Mersenne premier

nombre premier de la forme (2^n)-1
(Redirigé depuis Nombre premier de Mersenne)

En mathématiques et plus précisément en arithmétique, un nombre de Mersenne est un nombre de la forme 2n − 1 (où n est un entier naturel non nul), un nombre de Mersenne premier (parfois nombre premier de Mersenne), est donc un nombre premier de cette forme. Ces nombres doivent leur nom au religieux érudit et mathématicien français du XVIIe siècle Marin Mersenne, mais, près de 2000 ans auparavant, Euclide les utilisait déjà pour étudier les nombres parfaits.

Le moine français Marin Mersenne (1588-1648).

Si un nombre de Mersenne 2n − 1 est premier, nécessairement n est premier, mais cette condition n'est pas suffisante : 2, 3, 5, 7 et 11 sont premiers, les nombres de Mersenne 22 − 1 = 3, 23 − 1 = 7, 25 − 1 = 31 et 27 − 1 = 127 sont bien premiers, mais le nombre de Mersenne 211 – 1 = 2047 = 23×89 ne l'est pas.

Il existe un test de primalité efficace pour les nombres de Mersenne, le test de primalité de Lucas-Lehmer, ce qui fait que les plus grands nombres premiers connus sont des nombres de Mersenne. Les nombres de Mersenne premiers sont pourtant rares : 51 sont connus début 2020. Leur recherche fait l'objet d'un projet de calcul collaboratif, le projet GIMPS. On ne sait pas s'il existe une infinité de nombres de Mersenne premiers.

MotivationModifier

Les nombres premiers de Mersenne sont liés aux nombres parfaits, qui sont les nombres « égaux à la somme de leurs diviseurs stricts ». C'est cette connexion qui a motivé historiquement l'étude des nombres premiers de Mersenne. Dès le IVe siècle av. J.-C., Euclide démontrait que si M = 2p – 1 est un nombre premier, alors M(M + 1)/2 = 2p–1(2p – 1) est un nombre parfait. Deux millénaires plus tard, au XVIIIe siècle, Euler prouvait que tous les nombres parfaits pairs ont cette forme. Aucun nombre parfait impair n'est connu.

DéfinitionModifier

Le n-ième nombre de Mersenne 2n -1 est parfois noté[1] Mn = 2n -1 (n ∈ ℕ*). Tous les nombres de Mersenne ne sont pas premiers, par exemple M4=24 – 1 = 15 = 3 × 5. En fait dès que n=kl est composé, Mn=2kl − 1 est composé, car 2k − 1, qui est strictement supérieur à 1 si k est strictement supérieur à 1, est un diviseur de 2kl − 1.

Un nombre de Mersenne Mn = 2n -1 ne peut donc être premier que si n est premier[2].

La réciproque est fausse : même si n est premier, le nombre de Mersenne Mn peut ne pas être premier. Le plus petit contre-exemple est M11 = 2047 = 23×89.

Propriétés des nombres de MersenneModifier

Les nombres de Mersenne ont les propriétés suivantes

  • Ils constituent la suite de Lucas U(3, 2) (la suite des répunits en base 2).
  • Par conséquent, pgcd(Mm, Mn) = Mpgcd(m,n) (pour tout m, n > 0). En particulier si m divise n alors Mm divise Mn. Donc si n n'est pas premier alors Mn n'est pas premier. Ainsi, lorsqu'on cherche des nombres de Mersenne premiers, on sait déjà qu'il faut se limiter à des Mp avec p premier. Il faut ensuite affûter les critères de sélection des nombres premiers p.
  • Tous les nombres de Mersenne Mn ≥ 7, premiers ou composés, sont des nombres brésiliens car Mn = (111...111)2 avec n fois la présence du chiffre 1 dans l'écriture en base 2. Le nombre 7 est d'ailleurs le plus petit nombre brésilien.
  • D'après le test de primalité de Lucas-Lehmer pour les nombres de Mersenne, pour un nombre premier p impair, Mp est premier si et seulement si Mp divise Sp–1, où S1 = 4 et pour k ≥ 1, Sk+1 = Sk2 – 2.
  • Si a divise Mp avec p premier impair alors :
     
  • Un théorème d'Euler entraîne que pour q premier supérieur ou égal à 5, Mq est premier si et seulement s'il existe un unique couple (x, y) tel que Mq =(2x)2 + 3(3y)2. Bas Jansen[3] a étudié Mq = x2 + dy2 pour d compris entre 0 et 48.
  • Soit q ≡ 3 (mod 4) premier. Alors, 2q + 1 est aussi premier si et seulement s'il divise Mq[4]. Ainsi, par exemple, M11 est divisible par 23.
  • Ramanujan a conjecturé (en 1913) que l'équation Mq = 6 + x2, appelée équation de Ramanujan-Nagell, n'a que cinq solutions : q = 3, 4, 5, 7 ou 15, ce qui fut démontré par Trygve Nagell en 1948.
  • La constante d'Erdős-Borwein  , définie comme la somme de la série des inverses des nombres de Mersenne (non nécessairement premiers), est irrationnelle[5].

HistoriqueModifier

Si Mn est premier alors n aussi. Marin Mersenne, moine de l'ordre des Minimes au début du XVIIe siècle, est l'auteur de cette proposition qu'il aurait par ailleurs démontrée[6][Information douteuse],[7]. Il fournit aussi une liste des nombres premiers « de Mersenne » jusqu’à l'exposant 257, qui se révélera fausse : elle incluait par erreur 67 et 257, et omettait 61, 89 et 107[8].

La réciproque est fausse : Mp peut être composé alors que p est premier ; le plus petit contre-exemple est M11 = 2047 = 23×89 : 11 est premier mais M11 ne l'est pas, comme rappelé encore en 1732 par Euler[9], qui mentionne, que c'est également le cas pour p = 23, 83, 131, 179, 191 et 239[9].

Pour que Mn soit premier, il faut que n soit premier, ce qui simplifie déjà la recherche de nombres de Mersenne premiers. Pour tester si un nombre de Mersenne Mp (avec p premier) est premier, il existe une méthode comparativement très rapide, développée à l'origine par Édouard Lucas en 1878 et améliorée par Derrick Lehmer dans les années 1930. C'est grâce à ce test exceptionnellement simple comparativement à la taille des nombres considérés que depuis longtemps les plus grands nombres premiers connus sont des nombres premiers de Mersenne.

Les quatre premiers nombres premiers de Mersenne étaient connus dès l'Antiquité. Le cinquième (213 – 1) a été découvert avant 1461 par un inconnu. Les deux suivants ont été trouvés par Pietro Cataldi en 1588. Plus d'un siècle plus tard, en 1750, Euler en trouva encore un. Le suivant dans l'ordre chronologique (mais non numérique) a été trouvé par Lucas en 1876, puis un par Ivan Pervouchine en 1883. Deux autres ont été trouvés au début du XXe siècle par R. E. Powers (en) en 1911 et en 1914.

La recherche pour les nombres premiers de Mersenne fut révolutionnée par l'introduction des calculateurs électroniques. La première identification d'un nombre de Mersenne par ce moyen eut lieu à 22 heures le par un ordinateur SWAC à l'Institut d'Analyse Numérique (Institute for Numerical Analysis) du campus de l'université de Californie à Los Angeles, sous la direction de Derrick Lehmer, avec un programme écrit par Raphael Robinson.

C'était le premier nombre premier de Mersenne identifié depuis 38 ans. Le suivant fut trouvé moins de deux heures plus tard par le même ordinateur, qui en trouva trois de plus dans les mois suivants.

En décembre 2018, 51 nombres premiers de Mersenne étaient connus, le plus grand étant M82 589 933, qui est aussi à la même date le plus grand nombre premier connu[10]. Comme plusieurs de ses prédécesseurs, il a été découvert par un calcul distribué sous l'égide du projet GIMPS, Great Internet Mersenne Prime Search (qui signifie « grande recherche par Internet de nombres premiers de Mersenne »).

Liste des nombres de Mersenne premiersModifier

On ne sait pas si l'ensemble des nombres de Mersenne premiers est fini ou infini (mais on conjecture qu’il est infini). En décembre 2018, 51 nombres de Mersenne premiers étaient connus[11] (suites  A000043 (p) et  A000668 (Mp)).

Historiquement, ils n'ont pas toujours été découverts par ordre croissant (exemples : le 12-ième, M127, le 29-ième M4423...).

Liste des nombres premiers de Mersenne connus[12]
rang p Mp Valeur de Mp en base dix Nombre
de chiffres
en base dix
Date de découverte Découvreur(s)
1 2 M2 3 1 Antiquité remarqué
(en tant que nombre premier)
par les mathématiciens grecs
2 3 M3 7 1
3 5 M5 31 2
4 7 M7 127 3
5 13 M13 8 191 4 Moyen Âge (XIIIe siècle) Ibn Fallus (1194-1239)
6 17 M17 131 071 6 1588 Cataldi
7 19 M19 524 287 6 1588 Cataldi
8 31 M31 2 147 483 647 10 1750 Euler
9 61 M61 2 305 843 009 213 693 951 19 1883 Pervouchine
10 89 M89 618970019…449562111 27 1911 Powers (en)
11 107 M107 162259276…010288127 33 1914 Powers[13]
12 127 M127 170141183…884105727 39 1876 Lucas
13 521 M521 686479766…115057151 157 30 janvier 1952 Robinson (SWAC)
14 607 M607 531137992…031728127 183 30 janvier 1952 Robinson (SWAC)
15 1 279 M1279 104079321…168729087 386 25 juin 1952 Robinson (SWAC)
16 2 203 M2203 147597991…697771007 664 7 octobre 1952 Robinson (SWAC)
17 2 281 M2281 446087557…132836351 687 9 octobre 1952 Robinson (SWAC)
18 3 217 M3217 259117086…909315071 969 8 septembre 1957 Riesel (BESK (en))
19 4 253 M4253 190797007…350484991 1 281 3 novembre 1961 Hurwitz (IBM)
20 4 423 M4423 285542542…608580607 1 332 3 novembre 1961 Hurwitz (IBM)
21 9 689 M9689 478220278…225754111 2 917 11 mai 1963 Gillies (en) (ILLIAC II)
22 9 941 M9941 346088282…789463551 2 993 16 mai 1963 Gillies (ILLIAC II)
23 11 213 M11213 281411201…696392191 3 376 2 juin 1963 Gillies (ILLIAC II)
24 19 937 M19937 431542479…968041471 6 002 4 mars 1971 Tuckerman (en) (IBM)
25 21 701 M21701 448679166…511882751 6 533 30 octobre 1978 Noll (en) et Nickel (CDC)
26 23 209 M23209 402874115…779264511 6 987 9 février 1979 Noll (CDC)
27 44 497 M44497 854509824…011228671 13 395 8 avril 1979 Nelson (en) et Slowinski (en)
(Cray Research)
28 86 243 M86243 536927995…433438207 25 962 25 septembre 1982 Slowinski (Cray)
29 110 503 M110503 521928313…465515007 33 265 28 janvier 1988 Colquitt et Welsh (NEC)
30 132 049 M132049 512740276…730061311 39 751 19 septembre 1983 Slowinski (Cray)
31 216 091 M216091 746093103…815528447 65 050 1er septembre 1985 Slowinski (Cray)
32 756 839 M756839 174135906…544677887 227 832 19 février 1992 Slowinski et Gage
33 859 433 M859433 129498125…500142591 258 716 10 janvier 1994 Slowinski et Gage
34 1 257 787 M1257787 412245773…089366527 378 632 3 septembre 1996 Slowinski et Gage
35 1 398 269 M1398269 814717564…451315711 420 921 13 novembre 1996 GIMPS / Joel Armengaud
36 2 976 221 M2976221 623340076…729201151 895 932 24 août 1997 GIMPS / Gordon Spence
37 3 021 377 M3021377 127411683…024694271 909 526 27 janvier 1998 GIMPS / Roland Clarkson
38 6 972 593 M6972593 437075744…924193791 2 098 960 1er juin 1999 GIMPS / Nayan Hajratwala
39 13 466 917 M13466917 924947738…256259071 4 053 946 14 novembre 2001 GIMPS / Michael Cameron
40[14] 20 996 011 M20996011 125976895…855682047 6 320 430 17 novembre 2003 GIMPS / Michael Shafer
41[15] 24 036 583 M24036583 299410429…733969407 7 235 733 15 mai 2004 GIMPS / Josh Findley
42[16] 25 964 951 M25964951 122164630…577077247 7 816 230 18 février 2005[17] GIMPS / Martin Nowak
43[18] 30 402 457 M30402457 315416475…652943871 9 152 052 15 décembre 2005 GIMPS / Cooper et Boone
44[19] 32 582 657 M32582657 124575026…053967871 9 808 358 4 septembre 2006 GIMPS / Cooper et Boone
45[20] 37 156 667 M37156667 202254405…308220927 11 185 272 6 septembre 2008 GIMPS / Elvenich
46[21] 42 643 801 M42643801 169873516…562314751 12 837 064 12 avril 2009 GIMPS / Odd Magnar Strindmo
47[22] 43 112 609 M43112609 316470269…697152511 12 978 189 23 août 2008 GIMPS / Smith
48 ?[11] 57 885 161 M57885161 581887266…724285951 17 425 170 25 janvier 2013 GIMPS / Cooper
49 ?[11] 74 207 281 M74207281 300376418…086436351 22 338 618 7 janvier 2016 GIMPS / Cooper
50 ?[10] 77 232 917 M77232917 467333183...762179071 23 249 425 3 janvier 2018 GIMPS / Jonathan Pace
51 ?[23] 82 589 933 M82589933 148894445...217902591 24 862 048 7 décembre 2018 GIMPS / Patrick Laroche

Liste de nombres de Mersenne non premiersModifier

Les neuf plus petits nombres de Mersenne non premiers mais d'indices premiers (venant s'intercaler entre les 1er et 9e nombres de Mersenne premiers, connus à la fin du XIXe siècle) sont les suivants :

No  p Mp Valeur de Mp
en base dix
Nombre de
chiffres
en base dix
Décomposition
1 11 M11 2 047 4 23 × 89
2 23 M23 8 388 607 7 47 × 178 481
3 29 M29 536 870 911 9 233 × 1 103 × 2 089
4 37 M37 137 438 953 471 12 223 × 616 318 177
5 41 M41 2 199 023 255 551 13 13 367 × 164 511 353
6 43 M43 8 796 093 022 207 13 431 × 9 719 × 2 099 863
7 47 M47 140 737 488 355 327 15 2 351 × 4 513 × 13 264 529
8 53 M53 9 007 199 254 740 991 16 6 361 × 69 431 × 20 394 401
9 59 M59 576 460 752 303 423 487 18 179 951 × 3 203 431 780 337

Le nombre M67, égal à 147 573 952 589 676 412 927, figurait dans la liste originelle de Mersenne ; cependant, Lucas montra en 1876 que ce nombre n'était pas premier, sans toutefois pouvoir exhiber ses facteurs. La factorisation de ce nombre (193 707 721 x 761 838 257 287) fut déterminée par Frank Nelson Cole en 1903[24].

GénéralisationsModifier

Nombres premiers de SolinasModifier

Les nombres premiers de Solinas[25] sont les nombres premiers de la forme p = f(2k) où f est un polynôme unitaire à coefficients entiers[26] de faible « poids de réduction modulaire » (une condition technique destinée à ce que les calculs de réduction modulo p soient rapides et qui, pour simplifier, est parfois remplacée par : les coefficients non nuls de f sont peu nombreux et valent ±1[27],[28],[29]). Solinas[25] donne une série d'exemples, dont le premier est f(t) = t – 1, de « poids » 1 (qui correspond aux nombres de Mersenne) et le dernier est f(t) = t4t3 + t2 + 1, de « poids » 4, mais qui inclut aussi f(t) = tdtd–1 + td–2 – … + (–1)d, de « poids » 3.

Nombres premiers dont l'écriture n'utilise pas un chiffre donnéModifier

Un nombre de Mersenne premier est un nombre premier dont l'écriture binaire ne comporte aucun 0[30]. De manière analogue on peut étudier dans les bases supérieures les nombres premiers dont l'écriture est dépourvue d'un certain chiffre[31]. Il a été prouvé en 2019 qu'il existe une infinité de nombres premiers dont le développement en base 10 ne comporte pas l'un quelconque des chiffres de 0 à 9[32].

RéférencesModifier

  1. (en) Eric W. Weisstein, « Mersenne Prime », sur MathWorld.
  2. De façon générale si n > 1 et an − 1 est premier, alors a = 2 et n est premier, car si a > 2 alors a − 1 divise an − 1 et si a = 2et n = kl alors 2k-1 divise 2n − 1, (en) G. H. Hardy et E. M. Wright, An introduction to the theory of numbers, University Press, Oxford, Oxford at the Clarendon Press, (ISBN 0-19-853310-1), p.15.
  3. (en) B. Jansen, On Mersenne primes of the form x2 + d.y2 (2002) thèse.
  4. Chris Caldwell, « Proof of a result of Euler and Lagrange on Mersenne Divisors », sur Prime Pages' list of proofs.
  5. (en) P. Erdős, « On arithmetical properties of Lambert series », J. Indian Math. Soc., vol. 12,‎ , p. 63–66 (lire en ligne).
  6. Roger Beslan, Daniel Lignon, Les maths : cent théorèmes, Le Polygraphe éditeur, 2008, 176 pages. Illustrations : Pascal Jousselin (ISBN 978-2-909051-38-3).
  7. Voir cependant (en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [détail des éditions], vol. 1, p. 12, note 59.
  8. (en) Raymond Clare Archibald (en), « Mersenne's Numbers », Scripta Mathematica, vol. 3,‎ , p. 112-119 (lire en ligne).
  9. a et b E26, informations sur la publication.
  10. a et b (en) « GIMPS Project Discovers Largest Known Prime Number: 282 589 933-1 », sur GIMPS, .
  11. a b et c On ne sait pas s'il existe ou non un ou plusieurs autres nombres de Mersenne premiers, entre le 47e (M43 112 609) et le 49e (M74 207 281). Dans cet intervalle, le classement est donc provisoire. Néanmoins, tous les exposants inférieurs au 50e ont été testés au moins une fois ; il est donc probable que le classement est exact. Notons que le 29e nombre premier de Mersenne fut découvert après le 30e et le 31e, de même que M43 112 609 fut découvert quinze jours avant M37 156 667, plus petit. De même le 46e (M42 643 801) a été découvert neuf mois après le 47e (M43 112 609).
  12. (en) « List of Known Mersenne Prime Numbers », sur GIMPS.
  13. (en) Chris Caldwell, « M107: Fauquembergue or Powers? », sur Prime Pages.
  14. Prouvé le 11 juillet 2010 comme étant bien le 40e, c'est-à-dire qu'il n'y pas d'autre nombre de Mersenne entre le 39e et celui-ci — voir (en) « Older and lower profile GIMPS Milestones ».
  15. Prouvé le premier décembre 2011 comme étant bien le 41e. Voir GIMPS Milestones.
  16. Prouvé le 20 décembre 2012 comme étant bien le 42e. Voir GIMPS Milestones.
  17. (en) Eric W. Weisstein, « 42nd Mersenne Prime Found », sur MathWorld Headline News, .
  18. Prouvé le 23 février 2014 comme étant bien le 43e. Voir GIMPS Milestones.
  19. Prouvé le 8 novembre 2014 comme étant bien le 44e. Voir GIMPS Milestones.
  20. Prouvé le 2 septembre 2016 comme étant bien le 45e. Voir GIMPS Milestones.
  21. Prouvé le 22 février 2018 comme étant bien le 46e. Voir GIMPS Milestones.
  22. Prouvé le 8 avril 2018 comme étant bien le 47e. Voir GIMPS Milestones.
  23. https://www.mersenne.org/primes/?press=M82589933
  24. N Gridgeman, « The search for perfect numbers », New Scientist, no 334,‎ , p. 86–88 (lire en ligne)
  25. a et b (en) Jerome A. Solinas, « Generalized Mersenne numbers — Technical Report CORR 99-39 », Center for Applied Cryptographic Research, University of Waterloo, .
  26. La suite  A165255 de l'OEIS, créée en septembre 2009 à la suite d'une interprétation hâtive (sur Wikipédia en anglais) de l'article de Solinas, donne, sous le nom de « Solinas primes », une liste de nombres premiers de la forme 2a ± 2b ± 1, où 0 < b < a. Cette définition est reprise dans des publications ultérieures.
  27. (en) N. Koblitz et A. Menezes (en), « Cryptography at high security levels », dans Nigel Paul Smart, Cryptography and Coding: 10th IMA International Conference Proceedings, Springer, (lire en ligne), p. 13-36.
  28. (en) José de Jesús Angel Angel et Guillermo Morales-Luna, « Counting Prime Numbers with Short Binary Signed Representation », sur IACR Cryptology ePrint Archive, .
  29. Ou encore : « f(t) is a low-degree polynomial with small integer coefficients », (en) J. A. Solinas, « Generalized Mersenne Prime », dans Encyclopedia of Cryptography and Security, , 2e éd. (1re éd. 2005), p. 509-510.
  30. En effet pour tout  ,   s'écrit en binaire comme un 1 suivi de   fois le chiffres 0. Le nombre qui le précède,   ne comporte donc en binaire que le chiffre 1 tout comme le nombre   s'écrit en base 10 uniquement avec le chiffre 9.
  31. (en) [vidéo] Numberphile, Primes without a 7 sur YouTube.
  32. (en) James Maynard, « Primes with restricted digits », Inventiones mathematicae,‎ (DOI 10.1007/s00222-019-00865-6, arXiv abs/1604.01041), accès libre.

Voir aussiModifier

Articles connexesModifier

Liens externesModifier