Nombre de Mersenne premier

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 XVII^e 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

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

Si $n$ n'est pas premier (par exemple le produit $n=qp$ où ni $q$ , ni $p$ n'est égal à 1) alors le nombre $2^{qp}-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\geq 0}$ est égale à : $\displaystyle 1+2^{p}+(2^{p})^{2}+...+(2^{p})^{q-1}={\frac {2^{qp}-1}{2^{p}-1}},$ on prouve que $2^{qp}-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'affuter 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{\pmod {8}}.$
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+1$ où $k$ 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 IV^e 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 XVIII^e 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 2¹¹-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 (2¹³-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 XX^e 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 30 janvier 1952 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 RobinsonRaphael 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 2^57 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 M_p=2^p-1 étaient connus^[2].

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

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

#	p	M_p	Valeur de M_p en base 10	Nombre de chiffres en base 10	Décomposition	Date de découverte	Découvreur
1	11	M₁₁	2 047	4	23 x 89	Antiquité ?	Inconnu
2	23	M₂₃	8 388 607	7	47 x 178 481
3	29	M₂₉	536 870 911	9	233 x 1 103 x 2 089
4	37	M₃₇	137 438 953 471	12	223 x 616 318 177
5	41	M₄₁	2 199 023 255 551	13	13 367 x 164 511 353
6	43	M₄₃	8 796 093 022 207	13	431 x 9 719 x 2 099 863
7	47	M₄₇	140 737 488 355 327	15	2 351 x 4 513 x 13 264 529
8	53	M₅₃	9 007 199 254 740 991	16	6 361 x 69 431 x 20 394 401
9	59	M₅₉	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 x² + d.y² (2002) thèse
↑ ^{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 42^e (M_24 036 583) et le 47^e (M_43 112 609). Dans cet intervalle, le classement est donc provisoire. Déjà le 29^e nombre premier de Mersenne fut découvert après le 30^e et le 31^e, de même que M_43 112 609 fut découvert quinze jours avant M_37 156 667, plus petit. De même le 46^e (M_42 643 801) a été découvert neuf mois après le 47^e (M_43 112 609).
↑ prouvé le 11 juillet 2010 comme étant bien le 40^e, c'est-à-dire qu'il n'y pas d'autre nombre de Mersenne entre le 39^e 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 41^e. Voir http://mersenne.org/report_milestones/
↑ prouvé le 20 décembre 2012 comme étant bien le 42^e. Voir http://mersenne.org/report_milestones/
↑ (en) Page d'accueil du GIMPS, Découverte du 48^e nombre premier de Mersenne

Voir aussi

Articles connexes

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 42^e : 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

Arithmétique et théorie des nombres

[1] (en) B. Jansen, On Mersenne primes of the form x² + d.y² (2002) thèse

[Note-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 42^e (M_24 036 583) et le 47^e (M_43 112 609). Dans cet intervalle, le classement est donc provisoire. Déjà le 29^e nombre premier de Mersenne fut découvert après le 30^e et le 31^e, de même que M_43 112 609 fut découvert quinze jours avant M_37 156 667, plus petit. De même le 46^e (M_42 643 801) a été découvert neuf mois après le 47^e (M_43 112 609).

[3] rouvé le 11 juillet 2010 comme étant bien le 40^e, c'est-à-dire qu'il n'y pas d'autre nombre de Mersenne entre le 39^e et celui-ci — voir la section « M(20996011) proven to be 40th Mersenne Prime » sur http://www.mersenne.org/

[4] rouvé le premier décembre 2011 comme étant bien le 41^e. Voir http://mersenne.org/report_milestones/

[5] rouvé le 20 décembre 2012 comme étant bien le 42^e. Voir http://mersenne.org/report_milestones/

[mp-6] (en) Page d'accueil du GIMPS, Découverte du 48^e nombre premier de Mersenne

[1]

[2]

[3]

[4]

[5]

[6]