Nombre premier de Mersenne - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Propriétés des nombres de Mersenne - Liste - Historique

Introduction

Marin Mersenne

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

Plus généralement, les nombres de Mersenne (pas nécessairement premiers, mais candidats à l'être) sont les nombres de la forme 2^p - 1, avec p premier. On utilise la notation M_p = 2^p - 1.

Les plus petits nombres premiers de Mersenne sont :

3 = 2²-1
7 = 2³-1
31 = 2⁵-1
127 = 2⁷-1
Mais 2047 = 2¹¹-1 = 23 x 89 est un nombre de Mersenne, mais non premier.

On démontre qu'un entier de la forme 2ⁿ-1 ne peut pas être premier si n n'est pas lui-même premier. Ainsi 2⁴-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 :

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 $(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 également distinct de 1.

Remarque : on peut également 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, lorsque l'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$ ).

#	p	M_p	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	8 191	4	XIII^e siècle	Ibn Fallus
6	17	131 071	6	1588	Cataldi
7	19	524 287	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	Powers
11	107	162259276…010288127	33	1914	Powers
12	127	170141183…884105727	39	1876	Lucas
13	521	686479766…115057151	157	30 janvier 1952	Robinson (Swac)
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	Riesel (Besk)
19	4 253	190797007…350484991	1 281	3 novembre 1961	Hurwitz (IBM)
20	4 423	285542542…608580607	1 332	3 novembre 1961	Hurwitz (IBM)
21	9 689	478220278…225754111	2 917	11 mai 1963	Gillies (Illiac)
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	Tuckerman (IBM)
25	21 701	448679166…511882751	6 533	30 octobre 1978	Noll & Glenn (CDC)
26	23 209	402874115…779264511	6 987	9 février 1979	Noll (CDC)
27	44 497	854509824…011228671	13 395	8 avril 1979	Nelson & Slowinski (Cray Research)
28	86 243	536927995…433438207	25 962	25 septembre 1982	Slowinski (Cray)
29	110 503	521928313…465515007	33 265	28 janvier 1988	Colquitt & Welsh (Nec)
30	132 049	512740276…730061311	39 751	19 septembre 1983	Slowinski (Cray)
31	216 091	746093103…815528447	65 050	1^er septembre 1985	Slowinski (Cray)
32	756 839	174135906…544677887	227 832	19 février 1992	Slowinski & Gage
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 / Joel 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	1^er juin 1999	GIMPS / Nayan Hajratwala
39	13 466 917	924947738…256259071	4 053 946	14 novembre 2001	GIMPS / Michael Cameron
40	20 996 011	125976895…855682047	6 320 430	17 novembre 2003	GIMPS / Michael Shafer
41	24 036 583	299410429…733969407	7 235 733	15 mai 2004	GIMPS / Josh Findley
42	25 964 951	122164630…577077247	7 816 230	18 février 2005	GIMPS / Martin Nowak
43	30 402 457	315416475…652943871	9 152 052	15 décembre 2005	GIMPS / Cooper & Boone
44	32 582 657	124575026…053967871	9 808 358	4 septembre 2006	GIMPS / Cooper & Boone
45	37 156 667	202254405…308220927	11 185 272	6 septembre 2008	GIMPS / Elvenich
46	42 643 801	169873516…562314751	12 837 064	12 avril 2009	GIMPS / Odd Magnar Strindmo
47	43 112 609	316470267…697152511	12 978 189	23 août 2008	GIMPS / Smith

Nombre premier de Mersenne - Définition

Introduction

Propriétés des nombres de Mersenne

Liste

Notes