Nombre de Mersenne premier

En mathématiques et plus précisément en arithmétique, un nombre de Mersenne est un nombre de la forme $2 n - 1$ (souvent[1] noté M_n), où n est un entier naturel non nul ; un nombre de Mersenne premier (ou nombre premier de Mersenne) est donc un nombre premier de cette forme. Ces nombres doivent leur nom au religieux érudit et mathématicien français du XVII^e siècle Marin Mersenne ; mais, près de 2 000 ans auparavant, Euclide les utilisait déjà pour étudier les nombres parfaits. Avant Mersenne, et même un certain temps après lui, la recherche des nombres de Mersenne premiers est intrinsèquement liée à celle des nombres parfaits.

Le moine français Marin Mersenne (1588-1648)

Si le nombre de Mersenne $2 n - 1$ est premier, alors n est premier. Par exemple, les nombres de Mersenne $22 - 1 = 3, 2 3 - 1 = 7$ sont premiers, et leurs exposants $2, 3$ le sont bien aussi. Cette condition que n soit premier est nécessaire pour que le nombre de Mersenne $2 n - 1$ soit premier. Par exemple, $1, 4$ ne sont pas premiers, et les nombres de Mersenne $21 - 1 = 1, 2 4 - 1 = 15 = 3 \times 5$ ne le sont effectivement pas. Mais cette condition n'est pas suffisante. Par exemple, $11$ est premier, mais le nombre de Mersenne $211 - 1 = 2 047 = 23 \times 89$ ne l'est pas.

Il existe un test de primalité efficace pour les nombres de Mersenne, le test de primalité de Lucas-Lehmer ; de ce fait, les plus grands nombres premiers connus sont des nombres de Mersenne. Les nombres de Mersenne premiers sont pourtant rares : seulement $51$ sont connus début 2022. On ne sait même pas s'il en existe une infinité.

La recherche de grands nombres de Mersenne premiers fait l'objet d'un projet de calcul collaboratif, le projet GIMPS.

Nombres de Mersenne et nombres parfaits

Les nombres premiers de Mersenne sont liés aux nombres parfaits, qui sont les nombres « égaux à la somme de leurs diviseurs stricts ». Historiquement, c'est cette connexion qui a motivé 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 sont de cette forme. Par ailleurs, aucun nombre parfait impair n'est connu.

Propriétés des nombres de Mersenne

Propriété fondamentale des nombres de Mersenne

Soit $n \in$ $\mathbb {N} ^{*}$ ; si n n'est pas premier, alors le n-ième nombre de Mersenne $(M n = 2 n - 1)$ n'est pas premier. En effet :

Si $n = 1$ , alors $M n = 2 1 - 1 = 1$ .
Si n = kl est composé, alors M_n = 2^kl − 1 est composé. En effet :
- $k > 1$ et $l > 1$ , donc $kl > k$ , et donc $2 kl - 1 > 2 k - 1 > 1$ ;
- $2 kl - 1 = (2 k - 1)\times(2 k (l -1) + 2 k (l -2) + ... + 2 k \times2 + 2 k + 1)$ .

Les deux plus petits exemples avec indices composés sont :
$4 = 2 \times 2, 6 = 2 \times 3$ sont composés, et $M 4 = 2 4 - 1 = 15 = 3 \times 5, M 6 = 2 6 - 1 = 63 = 3 2 \times 7$ sont bien composés.

Plus précisément :
$2$ divise $4, 6$ , et $M 2 = 3$ divise bien $M 4 = 15, M 6 = 63$ .

Autrement dit (contraposée) :
Soit $n \in$ $\mathbb {N} ^{*}$ ; si le n-ième nombre de Mersenne $(M n = 2 n - 1)$ est premier, alors n est premier[2].

Les huit plus petits exemples sont :
$M 2 = 2 2 - 1 = 3, M 3 = 2 3 - 1 = 7, M 5 = 2 5 - 1 = 31, M 7 = 2 7 - 1 = 127, M 13 = 2 13 - 1 = 8 191, M 17 = 2 17 - 1 = 131 071, M 19 = 2 19 - 1 = 524 287, M 31 = 2 31 - 1 = 2 147 483 647$ ( A000668) sont premiers, et $2, 3, 5, 7, 13, 17, 19, 31$ ( A000043) sont bien premiers.

La réciproque est fausse. En effet :
Soit $n \in$ $\mathbb {N} ^{*}$ ; même si n est premier, le n-ième nombre de Mersenne $(M n = 2 n - 1)$ peut ne pas être premier.

Les trois plus petits contre-exemples sont :
$11$ , $23$ , $29$ ( A054723) sont premiers, mais $M 11 = 2 11 - 1 = 2 047 = 23 \times 89, M 23 = 2 23 - 1 = 8 388 607 = 47 \times 178 481, M 29 = 2 29 - 1 = 536 870 911 = 233 \times 1 103 \times 2 089$ ( A065341) sont composés[3].

Conséquences :
Pour trouver des nombres de Mersenne premiers, on sait déjà qu'il faut se limiter à des M_p avec p premier, mais que ce n'est pas suffisant. Il faut ensuite affûter les critères de sélection des nombres premiers p.

Autres propriétés des nombres de Mersenne

Ils constituent la suite des répunits en base 2.
Conséquence :
Pour tous entiers $m \geq 1$ et $n \geq 1, pgcd (M m, M n) = M pgcd(m, n)$ .
En particulier, si m divise n, alors M_m divise M_n. Donc, si n n'est pas premier, alors M_n n'est pas premier.

Exemple :

pgcd(M 4, M 6) = pgcd(2 4 - 1, 2 6 - 1) = pgcd(15, 63) = 3 = 2 2 - 1 = M 2 = M pgcd(4,6)

.

Tous les nombres de Mersenne $M n \geq 7$ , premiers ou composés, sont des nombres brésiliens. En effet :
$M n = (111...111) 2$ avec n fois la présence du chiffre $1$ dans l'écriture en base $2$ .
Le nombre $7$ est d'ailleurs le plus petit nombre brésilien.
D'après le test de primalité de Lucas-Lehmer pour les nombres de Mersenne, pour un nombre premier p impair, M_p est premier si et seulement si M_p divise $S p -1$ , où $S 1 = 4$ et pour tout $n \geq 1, S n +1 = S n 2 - 2$ .

Les six plus petits termes de cette suite de Lucas-Lehmer sont :

S 1 = 4, S 2 = 4 2 - 2 = 14, S 3 = 14 2 - 2 = 194, S 4 = 194 2 - 2 = 37 634, S 5 = 37 634 2 - 2 = 1 416 317 954, S 6 = 1 416 317 954 2 - 2 = 2 005 956 546 822 746 114

(voir la suite A003010 de l'OEIS).

(

M 2 = 3

ne divise pas

S 1 = 4

mais

2

est pair, et

M 2 = 3

est bien premier.)

M 3 = 7

divise

S 2 = 14 = 2 \times 7, M 5 = 31

divise

S 4 = 37 634 = 2 \times 31 \times 607, M 7 = 127

divise

S 6 = 2 005 956 546 822 746 114 = 2 \times 127 \times 7 897 466 719 774 591

, et

M 3 = 7, M 5 = 31, M 7 = 127

sont bien premiers.

M 4 = 15 = 3 \times 5

ne divise pas

S 3 = 194 = 2 \times 97, M 6 = 63 = 3 2 \times 7

ne divise pas

S 5 = 1 416 317 954 = 2 \times 708 158 977

, et

M 4, M 6

sont bien composés[3].

Si a divise M_p avec p premier impair, alors : $a\equiv 1{\pmod {2p}}\quad {\text{et}}\quad a\equiv \pm 1{\pmod {8}}.$
Un théorème d'Euler entraîne que pour q premier $\geq 5$ ,
M_q est premier si et seulement s'il existe un unique couple $(x, y)$ d'entiers $\geq 1$ tel que $M q = (2 x) 2 + 3(3 y) 2$ .

Exemples :
Pour

M 5 = 31 : q = 5

est premier

\geq 5; (2 \times 1) 2 + 3 (3 \times 1) 2 = 31

; ni x ni y ne peut diminuer, donc ni y ni x ne peut augmenter ; donc il existe un unique couple

(x, y)

d'entiers

\geq 1

tel que

(2 x) 2 + 3 (3 y) 2 = 31

(à savoir

(1, 1)

) ; et

M 5 = 31

est bien premier.
Pour

M 11 = 2 047 : q = 11

est premier

\geq 5; 2 047

est impair et

(2 x) 2

est pair, donc y doit être impair ;

2 047 - 3 (3 \times 1) 2 = 2 020 = 2 2 \times 5 \times 101, 2 047 - 3 (3 \times 3) 2 = 1 804 = 2 2 \times 11 \times 41, 2 047 - 3 (3 \times 5) 2 = 1 372 = 2 2 \times 7 3, 2 047 - 3 (3 \times 7) 2 = 724 = 2 2 \times 181

ne sont pas des carrés, et

2 047 - 3 (3 \times 9) 2 = -140 < 0

; donc il n'existe aucun couple

(x, y)

d'entiers

\geq 1

tel que

(2 x) 2 + 3 (3 y) 2 = 2 047

; et

M 11 = 2 047 = 23 \times 89

n'est effectivement pas premier.

(Bas Jansen[4] a étudié

M q = x 2 + d\cdoty 2

pour d compris entre

0

et

48

.)

Si $q \equiv 3 (mod 4)$ est premier, alors :
$2 q + 1$ est aussi premier si et seulement si $2 q + 1$ divise M_q[5].

Exemples :

7 = 3 + 1 \times 4, 7

est premier,

2 \times 7 + 1 = 15 = 3 \times 5

ne divise pas

M 7 = 127

, et

15

n'est effectivement pas aussi premier.

11 = 3 + 2 \times 4, 11

est premier,

2 \times 11 + 1 = 23

divise

M 11 = 2 047 = 23 \times 89

, et

23

est effectivement aussi premier.

Ramanujan a conjecturé (en 1913) que l'équation $M q = 6 + x 2$ , appelée équation de Ramanujan-Nagell, n'a que cinq solutions : $(q, x) \in {(3, 1), (4, 3), (5, 5), (7, 11), (15, 181)}$ ; ce fut démontré par Trygve Nagell en 1948.
La constante d'Erdős-Borwein $\sum _{n=1}^{\infty }{\frac {1}{2^{n}-1}}$ , définie comme la somme de la série des inverses des nombres de Mersenne (premiers ou non), est irrationnelle[6].

Historique

Historique des outils théoriques

Marin Mersenne, moine de l'ordre des Minimes au début du XVII^e siècle, est l'auteur de la proposition : si M_n est premier, alors n aussi ; il l'aurait par ailleurs démontrée[7]^{[Information douteuse]}^,[8].

En 1732, Euler rappelle que la réciproque est fausse : M_p peut être composé alors que p est premier. Il donne le plus petit contre-exemple : 11 est premier mais $M 11 = 2 047 = 23 \times 89$ ne l'est pas[9]; il mentionne que c'est aussi le cas pour $p = 23, 83, 131, 179, 191$ , et $239$ [9].

En 1878, Édouard Lucas développe une méthode pour tester si un nombre de Mersenne M_p (avec p premier) est premier. Dans les années 1930, Derrick Lehmer l'améliore. Le test de primalité de Lucas-Lehmer pour les nombres de Mersenne est exceptionnellement simple comparativement à la taille des nombres considérés. Grâce à ce test très rapide, depuis longtemps les plus grands nombres premiers connus sont des nombres premiers de Mersenne.

Historique des nombres de Mersenne premiers découverts

Les quatre premiers nombres premiers de Mersenne sont connus dès l'Antiquité. Au XII^e siècle, Ibn Fallus donne une liste de nombres parfaits dans un commentaire de l'introduction à l'arithmétique de Nicomaque. On y trouve ceux correspondant aux cinquième, sixième, et septième nombres de Mersenne. Mais il ne fournit aucun calcul et sa liste comporte des erreurs, qui peuvent laisser penser qu'il s'est appuyé sur des hypothèses fausses ou insuffisantes, et n'a pas vérifié la primalité de ces nombres de Mersenne[10]. On trouve le cinquième ( $213 - 1$ ) dans un manuscrit anonyme daté de 1456 ou 1461. Les deux suivants ( $217 - 1$ et $219 - 1$ ) sont donnés par Pietro Cataldi en 1588. Au début du XVII^e siècle, Marin Mersenne fournit une liste des nombres premiers « de Mersenne » jusqu’à l'exposant 257, qui se révélera fausse : elle inclut par erreur 67 et 257, et omet 61, 89, et 107[11].

Table des prévisions de Mersenne sur `M_p` pour `p` premier $\leq 263$

P : `M_p` est premier — : `M_p` n'est pas premier Cyan : Mersenne l'avait prévu Rose : il avait prévu le contraire
`p`	2	3	5	7	11	13	17	19
`M_p`	P	P	P	P	—	P	P	P
`p`	23	29	31	37	41	43	47	53
`M_p`	—	—	P	—	—	—	—	—
`p`	59	61	67	71	73	79	83	89
`M_p`	—	P	—	—	—	—	—	P
`p`	97	101	103	107	109	113	127	131
`M_p`	—	—	—	P	—	—	P	—
`p`	137	139	149	151	157	163	167	173
`M_p`	—	—	—	—	—	—	—	—
`p`	179	181	191	193	197	199	211	223
`M_p`	—	—	—	—	—	—	—	—
`p`	227	229	233	239	241	251	257	263
`M_p`	—	—	—	—	—	—	—	—

En 1750, Euler vérifie que $231 - 1$ est premier. Le suivant dans l'ordre chronologique (mais non numérique), $2127 - 1$ , est trouvé par Lucas en 1876 ; puis $261 - 1$ est démontré premier par Ivan Pervouchine en 1883. Encore deux autres sont trouvés au début du XX^e siècle par R. E. Powers (en) en 1911 et en 1914.

La recherche des nombres premiers de Mersenne est révolutionnée par l'utilisation des calculateurs électroniques. La première identification d'un nombre de Mersenne par ce moyen a 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 Robinson.

C'est le premier nombre premier de Mersenne identifié depuis $38$ ans. Le suivant est découvert moins de deux heures plus tard par le même ordinateur, qui en trouve trois de plus dans les mois suivants.

En décembre 2018, $51$ nombres premiers de Mersenne sont connus, le plus grand étant M_82 589 933, qui est aussi à la même date le plus grand nombre premier connu[12]. Comme plusieurs de ses prédécesseurs, il est 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

On ne sait pas si l'ensemble des nombres de Mersenne premiers est fini ou infini (mais on conjecture qu’il est infini). En décembre 2018, $51$ nombres de Mersenne premiers étaient connus[13] (suite A000043 pour p, et suite A000668 pour M_p).

Historiquement, ils ne furent pas toujours découverts par ordre croissant. Par exemple : en 1983 fut trouvé le 30^e, M_{132 049} ; en 1988 fut trouvé le 29^e, M_{110 503}.

Liste des nombres premiers de Mersenne connus[14]
Rang	`p`	`M_p`	Écriture de `M_p` en base 10	Nombre de chiffres en base 10	Date de découverte	Découvreur(s)
1	2	`M`₂	3	1	Antiquité	remarqué (en tant que nombre premier) par les mathématiciens grecs
2	3	`M`₃	7	1
3	5	`M`₅	31	2
4	7	`M`₇	127	3
5	13	`M`₁₃	8 191	4	XV^e siècle	manuscrit anonyme (1456 ou 1461)
6	17	`M`₁₇	131 071	6	1588	Cataldi
7	19	`M`₁₉	524 287	6	1588	Cataldi
8	31	`M`₃₁	2 147 483 647	10	1750	Euler
9	61	`M`₆₁	2 305 843 009 213 693 951	19	1883	Pervouchine
10	89	`M`₈₉	618970019…449562111	27	1911	Powers (en)
11	107	M₁₀₇	162259276…010288127	33	1914	Powers[15]
12	127	M₁₂₇	170141183…884105727	39	1876	Lucas
13	521	M₅₂₁	686479766…115057151	157	30 janvier 1952	Robinson (SWAC)
14	607	M₆₀₇	531137992…031728127	183	30 janvier 1952	Robinson (SWAC)
15	1 279	M₁₂₇₉	104079321…168729087	386	25 juin 1952	Robinson (SWAC)
16	2 203	M₂₂₀₃	147597991…697771007	664	7 octobre 1952	Robinson (SWAC)
17	2 281	M₂₂₈₁	446087557…132836351	687	9 octobre 1952	Robinson (SWAC)
18	3 217	M₃₂₁₇	259117086…909315071	969	8 septembre 1957	Riesel (BESK (en))
19	4 253	M₄₂₅₃	190797007…350484991	1 281	3 novembre 1961	Hurwitz (IBM)
20	4 423	M₄₄₂₃	285542542…608580607	1 332	3 novembre 1961	Hurwitz (IBM)
21	9 689	M₉₆₈₉	478220278…225754111	2 917	11 mai 1963	Gillies (en) (ILLIAC II)
22	9 941	M₉₉₄₁	346088282…789463551	2 993	16 mai 1963	Gillies (ILLIAC II)
23	11 213	M₁₁₂₁₃	281411201…696392191	3 376	2 juin 1963	Gillies (ILLIAC II)
24	19 937	M₁₉₉₃₇	431542479…968041471	6 002	4 mars 1971	Tuckerman (en) (IBM)
25	21 701	M₂₁₇₀₁	448679166…511882751	6 533	30 octobre 1978	Noll (en) et Nickel (CDC)
26	23 209	M₂₃₂₀₉	402874115…779264511	6 987	9 février 1979	Noll (CDC)
27	44 497	M₄₄₄₉₇	854509824…011228671	13 395	8 avril 1979	Nelson (en) et Slowinski (en) (Cray Research)
28	86 243	M₈₆₂₄₃	536927995…433438207	25 962	25 septembre 1982	Slowinski (Cray)
29	110 503	M₁₁₀₅₀₃	521928313…465515007	33 265	28 janvier 1988	Colquitt et Welsh (NEC)
30	132 049	M₁₃₂₀₄₉	512740276…730061311	39 751	19 septembre 1983	Slowinski (Cray)
31	216 091	M₂₁₆₀₉₁	746093103…815528447	65 050	1^er septembre 1985	Slowinski (Cray)
32	756 839	M₇₅₆₈₃₉	174135906…544677887	227 832	19 février 1992	Slowinski et Gage
33	859 433	M₈₅₉₄₃₃	129498125…500142591	258 716	10 janvier 1994	Slowinski et Gage
34	1 257 787	M_1257787	412245773…089366527	378 632	3 septembre 1996	Slowinski et Gage
35	1 398 269	M_1398269	814717564…451315711	420 921	13 novembre 1996	GIMPS / Joel Armengaud
36	2 976 221	M_2976221	623340076…729201151	895 932	24 août 1997	GIMPS / Gordon Spence
37	3 021 377	M_3021377	127411683…024694271	909 526	27 janvier 1998	GIMPS / Roland Clarkson
38	6 972 593	M_6972593	437075744…924193791	2 098 960	1^er juin 1999	GIMPS / Nayan Hajratwala
39	13 466 917	M_13466917	924947738…256259071	4 053 946	14 novembre 2001	GIMPS / Michael Cameron
40[16]	20 996 011	M_20996011	125976895…855682047	6 320 430	17 novembre 2003	GIMPS / Michael Shafer
41[17]	24 036 583	M_24036583	299410429…733969407	7 235 733	15 mai 2004	GIMPS / Josh Findley
42[18]	25 964 951	M_25964951	122164630…577077247	7 816 230	18 février 2005[19]	GIMPS / Martin Nowak
43[20]	30 402 457	M_30402457	315416475…652943871	9 152 052	15 décembre 2005	GIMPS / Cooper et Boone
44[21]	32 582 657	M_32582657	124575026…053967871	9 808 358	4 septembre 2006	GIMPS / Cooper et Boone
45[22]	37 156 667	M_37156667	202254405…308220927	11 185 272	6 septembre 2008	GIMPS / Elvenich
46[23]	42 643 801	M_42643801	169873516…562314751	12 837 064	12 avril 2009	GIMPS / Odd Magnar Strindmo
47[24]	43 112 609	M_43112609	316470269…697152511	12 978 189	23 août 2008	GIMPS / Smith
48[25]	57 885 161	M_57885161	581887266…724285951	17 425 170	25 janvier 2013	GIMPS / Cooper
49 ?[13]	74 207 281	M_74207281	300376418…086436351	22 338 618	7 janvier 2016	GIMPS / Cooper
50 ?[12]	77 232 917	M_77232917	467333183...762179071	23 249 425	3 janvier 2018	GIMPS / Jonathan Pace
51 ?[26]	82 589 933	M_82589933	148894445...217902591	24 862 048	7 décembre 2018	GIMPS / Patrick Laroche

Liste de nombres de Mersenne non premiers mais d'indices premiers

Les neuf plus petits nombres de Mersenne non premiers mais d'indices premiers (venant s'intercaler entre les 1^er et 9^e nombres de Mersenne premiers, connus à la fin du XIX^e siècle) sont :

N^o	`p` (suite A054723 de l'OEIS)	`M_p`	Écriture de `M_p` en base 10 (suite A065341 de l'OEIS)	Nombre de chiffres en base 10	Décomposition[3]
1	11	`M`₁₁	2 047	4	23 × 89
2	23	`M`₂₃	8 388 607	7	47 × 178 481
3	29	`M`₂₉	536 870 911	9	233 × 1 103 × 2 089
4	37	`M`₃₇	137 438 953 471	12	223 × 616 318 177
5	41	`M`₄₁	2 199 023 255 551	13	13 367 × 164 511 353
6	43	`M`₄₃	8 796 093 022 207	13	431 × 9 719 × 2 099 863
7	47	`M`₄₇	140 737 488 355 327	15	2 351 × 4 513 × 13 264 529
8	53	`M`₅₃	9 007 199 254 740 991	16	6 361 × 69 431 × 20 394 401
9	59	`M`₅₉	576 460 752 303 423 487	18	179 951 × 3 203 431 780 337

Le 10^e nombre de Mersenne non premier mais d'indice premier, $M 67 = 147 573 952 589 676 412 927$ , figurait dans la liste originelle de Mersenne ; mais Lucas montra en 1876 que ce nombre n'est pas premier, sans toutefois pouvoir exhiber ses facteurs. La factorisation $M 67 = 193 707 721 \times 761 838 257 287$ fut déterminée par Frank Nelson Cole en 1903[27].

Généralisations

Suite de Lucas

Les nombres de Mersenne (premiers ou non) sont les répunits en base 2. La suite $\left({\frac {b^{n}-1}{b-1}}\right)_{n\in \mathbb {N} ^{*}}$ des répunits en base b est la suite de Lucas U(b + 1, b). Or toute suite de Lucas U(P, Q) avec P et Q premiers entre eux est à divisibilité forte. Par le même raisonnement que pour la suite des nombres de Mersenne (voir supra), une condition nécessaire (mais non suffisante) pour que le n-ième terme d'une telle suite soit premier est donc que n le soit également.

Nombres premiers de Solinas

Les nombres premiers de Solinas[28] sont les nombres premiers de la forme p = f(2^k) où f est un polynôme unitaire à coefficients entiers[29] de faible « poids de réduction modulaire » (une condition technique destinée à ce que les calculs de réduction modulo p soient rapides et qui, pour simplifier, est parfois remplacée par : les coefficients non nuls de f sont peu nombreux et valent ±1[30]^,[31]^,[32]). Solinas[28] donne une série d'exemples, dont le premier est f(t) = t – 1, de « poids » 1 (qui correspond aux nombres de Mersenne) et le dernier est f(t) = t⁴ – t³ + t² + 1, de « poids » 4, mais qui inclut aussi f(t) = t^d – t^d–1 + t^d–2 – … + (–1)^d, de « poids » 3.

Nombres premiers dont l'écriture n'utilise pas un chiffre donné

Puisque les nombres de Mersenne sont les répunits en base 2, leur écriture binaire ne comporte aucun 0. De manière analogue, on peut étudier dans les bases supérieures les nombres premiers dont l'écriture est dépourvue d'un certain chiffre[33]. Il a été prouvé en 2019 qu'il existe une infinité de nombres premiers dont le développement en base 10 ne comporte pas l'un quelconque des chiffres de 0 à 9[34].

Répartition des nombres de Mersenne premiers

Les nombres de Mersenne premiers sont rares. On ne sait pas s'il en existe une infinité. Une conjecture est que le nombre de ceux qui sont inférieurs à un réel x donné est asymptotiquement proportionnel à $ln (ln x)$ , soit une croissance très lente et de plus en plus lente[35]. Plus précisément, selon une conjecture due à Lenstra et Pomerance, puis reformulée et complétée par Wagstaff, il y aurait asymptotiquement $e γ / ln 2 ln (ln x)$ nombres de Mersenne premiers inférieurs à x[35].

Si la conjecture était réalisée, le nombre $c (t)$ d'exposants p inférieurs à t tels que $2 p - 1$ est premier serait asymptotiquement proportionnel à $ln t$ . Une estimation fondée sur les $51$ nombres premiers connus en mars 2022 donne $c (t) = 2,50508 ln t$ [1].

Notes et références

(en) Eric W. Weisstein, « Mersenne Prime », sur MathWorld.
De façon générale :
Soient a > 1 et n > 1 ; si aⁿ − 1 est premier, alors a = 2 et n est premier. En effet :
- Si $a > 2$ , alors $a n - 1 > a - 1 > 1$ ; or $a - 1$ divise $a n - 1$ : absurde. Donc $a = 2$ .
- Si $n = kl$ , alors $2 k - 1$ divise $2 n - 1$ : absurde. Donc n est premier.
  (en) G. H. Hardy et E. M. Wright, An introduction to the theory of numbers, University Press, Oxford, Oxford at the Clarendon Press, 1968 (ISBN 0-19-853310-1), p.15.
« Décomposition en Facteurs Premiers - Factorisation en Ligne », sur www.dcode.fr (consulté le 23 mars 2022)
(en) B. Jansen, On Mersenne primes of the form x² + d·y² (2002), thèse.
(en) Chris Caldwell, « Proof of a result of Euler and Lagrange on Mersenne Divisors », sur Prime Pages' list of proofs.
(en) P. Erdős, « On arithmetical properties of Lambert series », J. Indian Math. Soc., vol. 12,‎ 1948, p. 63–66 (lire en ligne).
Roger Beslan, Daniel Lignon, Les maths : cent théorèmes, Le Polygraphe éditeur, 2008, 176 pages. Illustrations : Pascal Jousselin (ISBN 978-2-909051-38-3).
Voir cependant (en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [détail des éditions], vol. 1, p. 12, note 59.
E26, informations sur la publication.
Roshdi Rashed, « Ibn al-haytham et les nombres parfaits », Historia Mathematica, vol. 16, n^o 4,‎ novembre 1989, p. 343–352 (ISSN 0315-0860, DOI 10.1016/0315-0860(89)90081-5, lire en ligne), p. 349-350.
(en) Raymond Clare Archibald (en), « Mersenne's Numbers », Scripta Mathematica, vol. 3,‎ 1935, p. 112-119 (lire en ligne).
(en) « GIMPS Project Discovers Largest Known Prime Number: 2^82 589 933 – 1 », sur GIMPS, 21 décembre 2018.
On ne sait pas s'il existe ou non un ou plusieurs autres nombres de Mersenne premiers, entre le 48^e (M_57 885 161) et le 49^e (M_74 207 281). Dans cet intervalle, le classement est donc provisoire. Néanmoins, tous les exposants inférieurs au 50^e ont été testés au moins une fois ; il est donc probable que le classement est exact. Notons que 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).
(en) « List of Known Mersenne Prime Numbers », sur GIMPS.
(en) Chris Caldwell, « M₁₀₇: Fauquembergue or Powers? », sur Prime Pages.
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 (en) « Older and lower profile GIMPS Milestones ».
Prouvé le premier décembre 2011 comme étant bien le 41^e. Voir GIMPS Milestones.
Prouvé le 20 décembre 2012 comme étant bien le 42^e. Voir GIMPS Milestones.
(en) Eric W. Weisstein, « 42nd Mersenne Prime Found », sur MathWorld Headline News, 26 février 2005.
Prouvé le 23 février 2014 comme étant bien le 43^e. Voir GIMPS Milestones.
Prouvé le 8 novembre 2014 comme étant bien le 44^e. Voir GIMPS Milestones.
Prouvé le 2 septembre 2016 comme étant bien le 45^e. Voir GIMPS Milestones.
Prouvé le 22 février 2018 comme étant bien le 46^e. Voir GIMPS Milestones.
Prouvé le 8 avril 2018 comme étant bien le 47^e. Voir GIMPS Milestones.
Prouvé le 6 octobre 2021 comme étant bien le 48^e. Voir GIMPS Milestones.
https://www.mersenne.org/primes/?press=M82589933
N Gridgeman, « The search for perfect numbers », New Scientist, n^o 334,‎ 1963, p. 86–88 (lire en ligne)
(en) Jerome A. Solinas, « Generalized Mersenne numbers — Technical Report CORR 99-39 », Center for Applied Cryptographic Research, University of Waterloo, 1999.
La suite A165255 de l'OEIS, créée en septembre 2009 suite à une interprétation hâtive (sur Wikipédia en anglais) de l'article de Solinas, donne, sous le nom de « Solinas primes », une liste de nombres premiers de la forme 2^a ± 2^b ± 1, où 0 < b < a. Cette définition est reprise dans des publications ultérieures.
(en) N. Koblitz et A. Menezes, « Cryptography at high security levels », dans Nigel Paul Smart, Cryptography and Coding: 10th IMA International Conference Proceedings, Springer, 2005 (lire en ligne), p. 13-36.
(en) José de Jesús Angel Angel et Guillermo Morales-Luna, « Counting Prime Numbers with Short Binary Signed Representation », sur IACR Cryptology ePrint Archive, 2006.
Ou encore : « $f(t)$ is a low-degree polynomial with small integer coefficients », (en) J. A. Solinas, « Generalized Mersenne Prime », dans Encyclopedia of Cryptography and Security, 2011, 2^e éd. (1^re éd. 2005), p. 509-510.
(en) [vidéo] Numberphile, Primes without a 7 sur YouTube.
(en) James Maynard, « Primes with restricted digits », Inventiones mathematicae, vol. 217, n^o 1,‎ 2019, p. 127-218 (DOI 10.1007/s00222-019-00865-6, arXiv 1604.01041, lire en ligne).
(en) Chris K. Caldwell, « Heuristics Model for the Distribution of Mersennes », sur The PrimePages: prime number research & records, University Tennessee at Martin

Voir aussi

Articles connexes

Liens externes

(en) Chris Caldwell, « Mersenne Primes: History, Theorems and Lists », sur Prime Pages
(en) Bas Jansen, « Mersenne primes and class field theory », sur Université de Leyde (thèse, 2012, dir. Hendrik Lenstra)

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[:0-1] (en) Eric W. Weisstein, « Mersenne Prime », sur MathWorld.

[2] De façon générale :
Soient $a > 1$ et $n > 1$ ; si $a n - 1$ est premier, alors $a = 2$ et n est premier. En effet :
Si $a > 2$ , alors $a n - 1 > a - 1 > 1$ ; or $a - 1$ divise $a n - 1$ : absurde. Donc $a = 2$ .

Si $n = kl$ , alors $2 k - 1$ divise $2 n - 1$ : absurde. Donc n est premier.
(en) G. H. Hardy et E. M. Wright, An introduction to the theory of numbers, University Press, Oxford, Oxford at the Clarendon Press, 1968 (ISBN 0-19-853310-1), p.15.

[3] Si $a > 2$ , alors $a n - 1 > a - 1 > 1$ ; or $a - 1$ divise $a n - 1$ : absurde. Donc $a = 2$ .

[4] Si $n = kl$ , alors $2 k - 1$ divise $2 n - 1$ : absurde. Donc n est premier.
(en) G. H. Hardy et E. M. Wright, An introduction to the theory of numbers, University Press, Oxford, Oxford at the Clarendon Press, 1968 (ISBN 0-19-853310-1), p.15.

[:1-3] « Décomposition en Facteurs Premiers - Factorisation en Ligne », sur www.dcode.fr (consulté le 23 mars 2022)

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

[5] (en) Chris Caldwell, « Proof of a result of Euler and Lagrange on Mersenne Divisors », sur Prime Pages' list of proofs.

[6] (en) P. Erdős, « On arithmetical properties of Lambert series », J. Indian Math. Soc., vol. 12,‎ 1948, p. 63–66 (lire en ligne).

[7] Roger Beslan, Daniel Lignon, Les maths : cent théorèmes, Le Polygraphe éditeur, 2008, 176 pages. Illustrations : Pascal Jousselin (ISBN 978-2-909051-38-3).

[8] Voir cependant (en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [détail des éditions], vol. 1, p. 12, note 59.

[E26-9] E26, informations sur la publication.

[10] Roshdi Rashed, « Ibn al-haytham et les nombres parfaits », Historia Mathematica, vol. 16, n^o 4,‎ novembre 1989, p. 343–352 (ISSN 0315-0860, DOI 10.1016/0315-0860(89)90081-5, lire en ligne), p. 349-350.

[11] (en) Raymond Clare Archibald (en), « Mersenne's Numbers », Scripta Mathematica, vol. 3,‎ 1935, p. 112-119 (lire en ligne).

[plusgrand-12] (en) « GIMPS Project Discovers Largest Known Prime Number: 2^82 589 933 – 1 », sur GIMPS, 21 décembre 2018.

[Note-13] On ne sait pas s'il existe ou non un ou plusieurs autres nombres de Mersenne premiers, entre le 48^e (M_57 885 161) et le 49^e (M_74 207 281). Dans cet intervalle, le classement est donc provisoire. Néanmoins, tous les exposants inférieurs au 50^e ont été testés au moins une fois ; il est donc probable que le classement est exact. Notons que 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).

[14] (en) « List of Known Mersenne Prime Numbers », sur GIMPS.

[15] (en) Chris Caldwell, « M₁₀₇: Fauquembergue or Powers? », sur Prime Pages.

[16] 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 (en) « Older and lower profile GIMPS Milestones ».

[17] Prouvé le premier décembre 2011 comme étant bien le 41^e. Voir GIMPS Milestones.

[18] Prouvé le 20 décembre 2012 comme étant bien le 42^e. Voir GIMPS Milestones.

[19] (en) Eric W. Weisstein, « 42nd Mersenne Prime Found », sur MathWorld Headline News, 26 février 2005.

[20] Prouvé le 23 février 2014 comme étant bien le 43^e. Voir GIMPS Milestones.

[21] Prouvé le 8 novembre 2014 comme étant bien le 44^e. Voir GIMPS Milestones.

[22] Prouvé le 2 septembre 2016 comme étant bien le 45^e. Voir GIMPS Milestones.

[23] Prouvé le 22 février 2018 comme étant bien le 46^e. Voir GIMPS Milestones.

[24] Prouvé le 8 avril 2018 comme étant bien le 47^e. Voir GIMPS Milestones.

[25] Prouvé le 6 octobre 2021 comme étant bien le 48^e. Voir GIMPS Milestones.

[26] ttps://www.mersenne.org/primes/?press=M82589933

[27] N Gridgeman, « The search for perfect numbers », New Scientist, n^o 334,‎ 1963, p. 86–88 (lire en ligne)

[Solinas-28] (en) Jerome A. Solinas, « Generalized Mersenne numbers — Technical Report CORR 99-39 », Center for Applied Cryptographic Research, University of Waterloo, 1999.

[29] La suite A165255 de l'OEIS, créée en septembre 2009 suite à une interprétation hâtive (sur Wikipédia en anglais) de l'article de Solinas, donne, sous le nom de « Solinas primes », une liste de nombres premiers de la forme 2^a ± 2^b ± 1, où 0 < b < a. Cette définition est reprise dans des publications ultérieures.

[30] (en) N. Koblitz et A. Menezes, « Cryptography at high security levels », dans Nigel Paul Smart, Cryptography and Coding: 10th IMA International Conference Proceedings, Springer, 2005 (lire en ligne), p. 13-36.

[31] (en) José de Jesús Angel Angel et Guillermo Morales-Luna, « Counting Prime Numbers with Short Binary Signed Representation », sur IACR Cryptology ePrint Archive, 2006.

[32] Ou encore : « $f(t)$ is a low-degree polynomial with small integer coefficients », (en) J. A. Solinas, « Generalized Mersenne Prime », dans Encyclopedia of Cryptography and Security, 2011, 2^e éd. (1^re éd. 2005), p. 509-510.

[33] (en) [vidéo] Numberphile, Primes without a 7 sur YouTube.

[34] (en) James Maynard, « Primes with restricted digits », Inventiones mathematicae, vol. 217, n^o 1,‎ 2019, p. 127-218 (DOI 10.1007/s00222-019-00865-6, arXiv 1604.01041, lire en ligne).

[PrimePages-35] (en) Chris K. Caldwell, « Heuristics Model for the Distribution of Mersennes », sur The PrimePages: prime number research & records, University Tennessee at Martin