Nombre premier de Mersenne

En mathématiques et plus exactement en arithmétique modulaire, un nombre premier de Mersenne est un nombre premier s'écrivant sous la forme 2 p - 1, p étant premier.



Catégories :

Arithmétique modulaire - Nombre premier - Nombre premier de Mersenne

Marin Mersenne

En mathématiques et plus exactement en arithmétique modulaire, un nombre premier de Mersenne est un nombre premier s'écrivant sous la forme 2p - 1, p étant premier. Ces nombres premiers doivent leur nom à un érudit et mathématicien français du XVIIe siècle, Marin Mersenne. Les nombres premiers de Mersenne sont , en base 2 (binaire), les répunits qui sont premiers.

D'une façon plus générale, les nombres de Mersenne (pas obligatoirement premiers, mais candidats à l'être) sont les nombres de la forme 2p - 1, avec p premier. On utilise la notation Mp = 2p - 1.

Les plus petits nombres premiers de Mersenne sont :

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

Propriétés des nombres de Mersenne

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

En effet, en remarquant que la suite des q premiers termes de la suite géométrique  (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  \displaystyle 2ˆ{q p}-1 est divisible par  \displaystyle 2ˆp -1 qui est différent de 1 dès que p est aussi différent de 1.

Remarque : on peut aussi utiliser la formule \displaystyle 1+2ˆq+(2ˆ{q})ˆ2+...+(2ˆ{q})ˆ{p-1} = \frac{2ˆ{q p}-1}{2ˆq -1}, pour prouver ce résultat.

Ainsi, quand on cherche des nombres premiers via les nombres de Mersenne, on sait déjà qu'il faut éviter les candidats comme  \displaystyle 2ˆ4 -1 (i. e. 15),  \displaystyle 2ˆ6 -1 (i. e. 63) ou  \displaystyle 2ˆ9 -1 (i. e. 511 = 7 \times 73).

L'idée est désormais d'affuter les critères de sélection des nombres premiers  \displaystyle p ...

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 M = 2p - 1 est un nombre premier, alors M (M+1) /2 = 2 (p-1) (2p - 1) est un nombre parfait. Deux millénaires plus tard, au XVIIIe siècle, Euler prouvait que l'ensemble des nombres parfaits pairs ont cette forme. Aucun nombre parfait impair n'est connu.

Ma divise Mp si a divise p. Par conséquent pour que Mp 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 : Mp peut être composé tandis que p est premier ; le plus petit exemple est 211-1 = 23×89.

Pour les nombres de Mersenne il existe une méthode (comparativement) particulièrement rapide pour déterminer s'ils sont premiers, développée à l'origine par Lucas en 1878 et perfectionnée par Derrick Lehmer dans les années 1930. On peut effectivement montrer que pour un nombre premier p impair Mp = 2p − 1 est premier si et uniquement si Mp divise Sp − 1, où S1 = 4 et pour k > 1, S_{k+1} = S_{k}ˆ2 -2.

Mersenne n'a pas découvert les nombres de Mersenne, mais il a apporté 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 Cataldi en 1588. Plus d'un siècle plus tard, en 1750, Euler en trouva toujours un. Le suivant dans l'ordre chronologique (mais non numérique) a été trouvé par Lucas en 1876, puis un par Pervushin en 1883. Deux autres ont été trouvés au début du XXe siècle par Powers 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 30 janvier 1952 par un ordinateur SWAC à l'Institut d'Analyse Numérique (Institute for Numerical Analysis) du campus de Université de Californie - Los Angeles, sous la direction de Derrick Lehmer, avec un programme rédigé par R. M. 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 juin 2009, 47 nombres premiers de Mersenne étaient connus, le plus grand étant 243 112 609-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 veut dire «grande recherche par Internet de nombres premiers de Mersenne»).

Liste

En juin 2009, 47 nombres premiers de Mersenne Mp=2p-1 étaient connus.

# p Mp Nombre
de chiffres
Date
de découverte
Découvreur
1 2 3 1 Antiquité Inconnu
2 3 7 1 Antiquité Inconnu
3 5 31 2 Antiquité Inconnu
4 7 127 3 Antiquité Inconnu
5 13 4 XIIIe siècle
6 17 6 1588 Cataldi
7 19 6 1588 Cataldi
8 31 2 147 483 647 10 1750 Euler
9 61 2 305 843 009 213 693 951 19 1883 Pervushin
10 89 618970019…449562111 27 1911
11 107 162259276…010288127 33 1914 Powers
12 127 170141183…884105727 39 1876 Lucas
13 521 686479766…115057151 157 30 janvier 1952
14 607 531137992…031728127 183 30 janvier 1952 Robinson (Swac)
15 1 279 104079321…168729087 386 25 juin 1952 Robinson (Swac)
16 2 203 147597991…697771007 664 7 octobre 1952 Robinson (Swac)
17 2 281 446087557…132836351 687 9 octobre 1952 Robinson (Swac)
18 3 217 259117086…909315071 969 8 septembre 1957
19 4 253 190797007…350484991 1 281 3 novembre 1961
20 4 423 285542542…608580607 1 332 3 novembre 1961 Hurwitz (IBM)
21 9 689 478220278…225754111 2 917 11 mai 1963
22 9 941 346088282…789463551 2 993 16 mai 1963 Gillies (Illiac)
23 11 213 281411201…696392191 3 376 2 juin 1963 Gillies (Illiac)
24 19 937 431542479…968041471 6 002 4 mars 1971
25 21 701 448679166…511882751 6 533 30 octobre 1978
26 23 209 402874115…779264511 6 987 9 février 1979 Noll (CDC)
27 44 497 854509824…011228671 13 395 8 avril 1979
28 86 243 536927995…433438207 25 962 25 septembre 1982 Slowinski (Cray)
29 110 503 521928313…465515007 33 265 28 janvier 1988
30 132 049 512740276…730061311 39 751 19 septembre 1983 Slowinski (Cray)
31 216 091 746093103…815528447 65 050 1er septembre 1985 Slowinski (Cray)
32 756 839 174135906…544677887 227 832 19 février 1992
33 859 433 129498125…500142591 258 716 10 janvier 1994 Slowinski & Gage
34 1 257 787 412245773…089366527 378 632 3 septembre 1996 Slowinski & Gage
35 1 398 269 814717564…451315711 420 921 13 novembre 1996 GIMPS / Jœl Armengaud
36 2 976 221 623340076…729201151 895 932 24 août 1997 GIMPS / Gordon Spence
37 3 021 377 127411683…024694271 909 526 27 janvier 1998 GIMPS / Roland Clarkson
38 6 972 593 437075744…924193791 2 098 960 1er juin 1999 GIMPS / Nayan Hajratwala
39 13 466 917 924947738…256259071 4 053 946 14 novembre 2001 GIMPS / Michæl Cameron
40[N 1] 20 996 011 125976895…855682047 6 320 430 17 novembre 2003 GIMPS / Michæl Shafer
41[N 1] 24 036 583 299410429…733969407 7 235 733 15 mai 2004 GIMPS / Josh Findley
42[N 1] 25 964 951 122164630…577077247 7 816 230 18 février 2005 GIMPS / Martin Nowak
43[N 1] 30 402 457 315416475…652943871 9 152 052 15 décembre 2005 GIMPS/ Cooper & Boone
44[N 1] 32 582 657 124575026…053967871 9 808 358 4 septembre 2006 GIMPS/ Cooper & Boone
45[N 1] 37 156 667 202254405…308220927 11 185 272 6 septembre 2008 GIMPS / Elvenich[1]
46[N 1] 42 643 801 169873516…562314751 12 837 064 12 avril 2009 GIMPS / Odd Magnar Strindmo
47[N 1] 43 112 609 316470267…697152511 12 978 189 23 août 2008 GIMPS / Smith[1]

Note

  1. On ne sait pas s'il existe ou non un ou plusieurs autres nombres premiers de Mersenne entre le 39e (M13 466 917) et le 47e (M43 112 609). Dans cet intervalle, le classement est par conséquent 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).

Voir aussi

Liens externes

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Nombre_premier_de_Mersenne.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu