« Nombre de Mersenne premier » : différence entre les versions
wikif : souligné non nécessaire |
→Liste de nombres de Mersenne non premiers : retrait lien rouge |
||
Ligne 161 : | Ligne 161 : | ||
! width=5% | # || width=5% | p || width=5% | M<sub>p</sub> || width=18% | Valeur de M<sub>p</sub> en base 10 || width=15% | Nombre de chiffres<br />en base 10 || width=20% | Décomposition || width=17%| Date de<br />découverte || width=15% | Découvreur |
! width=5% | # || width=5% | p || width=5% | M<sub>p</sub> || width=18% | Valeur de M<sub>p</sub> en base 10 || width=15% | Nombre de chiffres<br />en base 10 || width=20% | Décomposition || width=17%| Date de<br />découverte || width=15% | Découvreur |
||
|- |
|- |
||
| 1 || 11 || M<sub>11</sub> || |
| 1 || 11 || M<sub>11</sub> || 2 047 || 4 || 23 x 89|| Antiquité ? || align="left" | ''Inconnu'' |
||
|- |
|- |
||
| 2 || 23 || M<sub>23</sub> || 8 388 607 || 7 || 47 x 178 481|| || align="left" | |
| 2 || 23 || M<sub>23</sub> || 8 388 607 || 7 || 47 x 178 481|| || align="left" | |
Version du 6 juin 2013 à 15:49
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 , avec 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 :
La sous-suite des nombres de Mersenne premiers est généralement notée
Les plus petits nombres de Mersenne premiers sont donc :
- ;
- ;
- ;
- ;
- Mais, , 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 ne peut pas être premier si n'est pas lui-même premier. Ainsi n'est pas un nombre de Mersenne, et n'est pas non plus premier.
Propriétés des nombres de Mersenne
Les nombres de Mersenne ont les propriétés suivantes :
- Si n'est pas premier (par exemple le produit où ni , ni n'est égal à 1) alors le nombre n'est pas premier.
En effet, en remarquant que la suite des premiers termes de la suite géométrique est égale à :on prouve que est divisible par qui est différent de 1 dès que est également distinct de 1. (On peut, dans ce raisonnement, intervertir les rôles de et .)
Ainsi, lorsque l'on cherche des nombres premiers via les nombres de Mersenne, on sait déjà qu'il faut éviter les candidats comme (i.e. 15), (i.e. 63) ou (i.e. 511 = 7×73).
L'idée est ensuite d'affuter les critères de sélection des nombres premiers … - est la somme de coefficients binomiaux moins 1 :
- Si divise ( premier) alors possède les propriétés suivantes :
- Un théorème d'Euler entraîne que : ( premier) est premier si et seulement s'il existe une unique paire telle que : avec supérieur ou égal à 5. Récemment, Bas Jansen[1] a étudié pour =0,48.
- Soit ≡ 3 (mod 4) premier. est aussi premier si et seulement si : divise [réf. nécessaire].
- Reix[Qui ?] a récemment montré que les nombres de Mersenne ( premier > 3), premiers ou non, s'écrivent : . Évidemment, si la paire est unique, alors est premier[réf. nécessaire].
- Ramanujan a montré que l'équation : a seulement trois solutions où est premier : 3, 5, et 7 (et deux solutions où est non premier).
- Tous les facteurs premiers d'un nombre de Mersenne associé au nombre premier sont de la forme où est un entier naturel. Deux nombres de Mersenne distincts sont toujours premiers entre eux.
Historique
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 est un nombre premier, alors 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.
divise si divise . Donc pour que soit premier, il faut que soit premier. Cela simplifie déjà la recherche de nombres premiers de Mersenne. La réciproque n'est pas vraie : peut être composé alors que 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 impair est premier si et seulement si divise , où et pour , .
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 .
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
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 694 000 | 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 (SWAC ) |
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 (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 non premiers
Les neuf premiers nombres de Mersenne non premiers (venant s'intercaler entre les 1er et 9ème 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 x 89 | Antiquité ? | Inconnu |
2 | 23 | M23 | 8 388 607 | 7 | 47 x 178 481 | ||
3 | 29 | M29 | 536 870 911 | 9 | 233 x 1 103 x 2 089 | ||
4 | 37 | M37 | 137 438 953 471 | 12 | 223 x 616 318 177 | ||
5 | 41 | M41 | 2 199 023 255 551 | 13 | 13 367 x 164 511 353 | ||
6 | 43 | M43 | 8 796 093 022 207 | 13 | 431 x 9 719 x 2 099 863 | ||
7 | 47 | M47 | 140 737 488 355 327 | 15 | 2 351 x 4 513 x 13 264 529 | ||
8 | 53 | M53 | 9 007 199 254 740 991 | 16 | 6 361 x 69 431 x 20 394 401 | ||
9 | 59 | M59 | 576 460 752 303 423 487 | 18 | 179 951 x 3 203 431 780 337 |
Notes et références
- (en) B. Jansen, On Mersenne primes of the form x2 + d.y2 (2002) thèse
- 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).
- 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/
- prouvé le premier décembre 2011 comme étant bien le 41e. Voir http://mersenne.org/report_milestones/
- prouvé le 20 décembre 2012 comme étant bien le 42e. Voir http://mersenne.org/report_milestones/
- (en) Page d'accueil du GIMPS, Découverte du 48e nombre premier de Mersenne
Voir aussi
Articles connexes
- Liste des grands nombres
- Nombre premier
- Liste de nombres premiers
- Nombre premier de Fermat
- Nombre parfait
- GIMPS
Liens externes
- (en) www.utm.edu « Mersenne Primes: History, Theorems and Lists » sur The prime number pages de Chris Caldwell
- (en) mathworld.wolfram.com Découverte du 42e : dépêche de février 2005 sur MathWorld Headline News
- (en) Eric W. Weisstein, « Mersenne number », sur MathWorld
- (en) Eric W. Weisstein, « Mersenne prime », sur MathWorld