Nombre de Mersenne premier

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Nombre premier de Mersenne)
Aller à : navigation, rechercher

En mathématiques et plus précisément en arithmétique modulaire, un nombre de Mersenne premier ou nombre premier de Mersenne est un nombre premier pouvant s'écrire sous la forme 2^p - 1, avec p lui-même entier premier. Ces nombres premiers doivent leur nom à un religieux érudit et mathématicien français du XVIIe siècle, Marin Mersenne. Les nombres de Mersenne premiers sont, en base 2 (binaire), les repunits qui sont premiers.

Plus généralement, les nombres de Mersenne, pas nécessairement premiers, mais candidats à l'être, constituent la suite des nombres  :

M_p=2^p-1.

La sous-suite des nombres de Mersenne premiers est généralement notée M1,...Mn

Les plus petits nombres de Mersenne premiers sont donc :

  • M1 = M_2 = 2^2 - 1 = 3 ;
  • M2 = M_3 = 2^3 - 1 = 7 ;
  • M3 = M_5 = 2^5 - 1 = 31 ;
  • M4 = M_7 = 2^7 - 1 = 127 ;
  • Mais,    M_{{11}} = 2^{{11}} - 1 = 2047 = 23*89, est un nombre de Mersenne non premier qui n'incrémente donc pas la notation « Mn ».

On démontre qu'un entier de la forme 2^n-1 ne peut pas être premier si n n'est pas lui-même premier. Ainsi 2^4-1=15 n'est pas un nombre de Mersenne, et n'est pas non plus premier.

Propriétés des nombres de Mersenne[modifier | modifier le code]

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

  • Si  n n'est pas premier (par exemple le produit  n = q p où ni q, ni p n'est égal à 1) alors le nombre  2^{q p} - 1 n'est pas premier.
    En effet, en remarquant que la suite des q premiers termes de la suite géométrique \scriptstyle(2^p)_{p \ge 0} est égale à :
    \displaystyle 1+2^p+(2^{p})^2+...+(2^{p})^{q-1} = \frac{2^{q p}-1}{2^p -1},
    on prouve que 2^{q p}-1 est divisible par 2^p -1 qui est différent de 1 dès que p est également distinct de 1. (On peut, dans ce raisonnement, intervertir les rôles de p et q.)
    Ainsi, lorsque l'on cherche des nombres premiers via les nombres de Mersenne, on sait déjà qu'il faut éviter les candidats comme 2^4 -1 (i.e. 15), 2^6 -1 (i.e. 63) ou 2^9 -1 (i.e. 511 = 7×73).
    L'idée est ensuite d'affûter les critères de sélection des nombres premiers p
  • M_n est la somme de coefficients binomiaux moins 1 :
     M_n = \sum_{i=0}^{n} {n \choose i}-1.
  • Si a divise M_q (q premier) alors a possède les propriétés suivantes :
    a \equiv 1\pmod{2q}\quad\text{et}\quad a \equiv \pm 1\pmod8.
  • Un théorème d'Euler entraîne que : M_q (q premier) est premier si et seulement s'il existe une unique paire  (x,y) telle que :  M_q = {(2x)}^2 + 3{(3y)}^2  avec q supérieur ou égal à 5. Récemment, Bas Jansen[1] a étudié  M_q = x^2 + dy^2 pour d=0,48.
  • Soit q ≡ 3 (mod 4) premier.  2q+1 est aussi premier si et seulement si : 2q+1 divise M_q[réf. nécessaire].
  • Reix[Qui ?] a récemment montré que les nombres de Mersenne M_q (q premier > 3), premiers ou non, s'écrivent :  M_q = {(8x)}^2 - {(3qy)}^2 = {(1+Sq)}^2 - {(Dq)}^2 . Évidemment, si la paire (x, y) est unique, alors M_q est premier[réf. nécessaire].
  • Ramanujan a montré que l'équation :  M_q = 6+x^2 a seulement trois solutions où q est premier : 3, 5, et 7 (et deux solutions où q est non premier).
  • Tous les facteurs premiers d'un nombre de Mersenne associé au nombre premier p sont de la forme 2kp+1k est un entier naturel. Deux nombres de Mersenne distincts sont toujours premiers entre eux.

Historique[modifier | modifier le code]

Les nombres premiers de Mersenne sont liés aux nombres parfaits, qui sont les nombres égaux à la somme de leurs diviseurs propres. 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=2^p-1 est un nombre premier, alors M(M+1)/2=2^{p-1}(2^p-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.

M_a divise M_p si a divise p. Donc pour que M_p soit premier, il faut que p soit premier. Cela simplifie déjà la recherche de nombres premiers de Mersenne. La réciproque n'est pas vraie : M_p peut être composé alors que p est premier ; le plus petit exemple est 211-1 = 23×89.

Pour les nombres de Mersenne il existe une méthode (comparativement) très rapide pour déterminer s'ils sont premiers, développée à l'origine par Édouard Lucas en 1878 et améliorée par Derrick Lehmer dans les années 1930. On peut effectivement montrer que pour un nombre premier p impair M_p = 2^p-1 est premier si et seulement si M_p divise S_{p-1}, où S_1 = 4 et pour k > 1, \scriptstyle S_{k+1}=S_k^2-2.

Mersenne n'a pas inventé les nombres de Mersenne, mais il a fourni une liste de nombres premiers de Mersenne jusqu’à l'exposant 257. Malheureusement cette liste était fausse : elle incluait par erreur 67 et 257, et omettait 61, 89 et 107.

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 Pervushin 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 (en).

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 février 2013, 48 nombres premiers de Mersenne étaient connus, le plus grand étant 257 885 161-1. 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 premiers connus[modifier | modifier le code]

En février 2013, 48 nombres de Mersenne premiers Mp=2p-1 étaient connus[2].

Historiquement, ils n'ont pas toujours été découverts par ordre croissant (exemples : M12, M29...).

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

Liste de nombres de Mersenne[modifier | modifier le code]

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

# p Mp Valeur de Mp en base 10 Nombre de chiffres
en base 10
Décomposition Date de
découverte
Découvreur
1 11 M11 2 047 4 23 × 89 Antiquité ? Inconnu
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    

Notes et références[modifier | modifier le code]

  1. (en) B. Jansen, On Mersenne primes of the form x2 + d.y2 (2002) thèse
  2. a, b, c, d, e, f et g On ne sait pas s'il existe ou non un ou plusieurs autres nombres de Mersenne premiers, entre le 42e (M24 036 583) et le 47e (M43 112 609). Dans cet intervalle, le classement est donc provisoire. Déjà 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).
  3. 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 la section « M(20996011) proven to be 40th Mersenne Prime » sur http://www.mersenne.org/
  4. prouvé le premier décembre 2011 comme étant bien le 41e. Voir http://mersenne.org/report_milestones/
  5. prouvé le 20 décembre 2012 comme étant bien le 42e. Voir http://mersenne.org/report_milestones/
  6. (en) Page d'accueil du GIMPS, Découverte du 48e nombre premier de Mersenne

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]