Liczby Mersenne’a: Liczby o jeden mniejsze od naturalnych potęg dwójki

Liczby Mersenne’a zostały tak nazwane na cześć francuskiego matematyka Marina Mersenne’a, który opublikował tablicę liczb pierwszych tego typu (jak się później okazało, błędną).

Liczba Mersenne’a ${\displaystyle M_{n}}$ jest równa sumie ciągu geometrycznego

${\displaystyle 2^{0}+2^{1}+2^{2}+2^{3}+\ldots +2^{n-1}.}$

Warunkiem koniecznym, żeby liczba ${\displaystyle M_{n}}$  była pierwsza jest, by ${\displaystyle n}$  było liczbą pierwszą.

Rzeczywiście, niech ${\displaystyle n=ab}$  będzie liczbą złożoną, gdzie ${\displaystyle a,b>1}$  są liczbami naturalnymi. Wówczas

${\displaystyle M_{n}=2^{n}-1=2^{ab}-1=(2^{a})^{b}-1^{b}=(2^{a}-1)(2^{a(b-1)}+2^{a(b-2)}+2^{a(b-3)}+\ldots +2^{a(b-b)})}$ 

również jest złożona.

Pierwszość wskaźnika ${\displaystyle n}$  nie jest jednak wystarczająca dla pierwszości liczby ${\displaystyle M_{n},}$  np.:

${\displaystyle M_{11}=2^{11}-1=23\cdot 89.}$ 

Liczby złożone Mersenne’a

Nie wiadomo, czy istnieje nieskończenie wiele liczb złożonych Mersenne’a o wskaźnikach pierwszych. Ich przykładami są:

${\displaystyle 2^{11}-1=2047=23\cdot 89}$ 
${\displaystyle 2^{23}-1=8388607=47\cdot 178481}$ 
${\displaystyle 2^{29}-1=536870911=233\cdot 1103\cdot 2089}$ 
${\displaystyle 2^{37}-1=137438953471=223\cdot 616318177}$ 
${\displaystyle 2^{43}-1=8796093022207=431\cdot 9719\cdot 2099863}$ 
${\displaystyle 2^{47}-1=140737488355327=2351\cdot 4513\cdot 13264529}$ 
${\displaystyle 2^{53}-1=9007199254740991=6361\cdot 69431\cdot 20394401}$ 
${\displaystyle 2^{59}-1=576460752303423487=179951\cdot 3203431780337}$ 
${\displaystyle 2^{83}-1=9671406556917033397649407=167\cdot 57912614113275649087721}$ 

Hipoteza byłaby prawdziwa, gdyby okazało się, że istnieje nieskończenie wiele liczb pierwszych Germain mających postać ${\displaystyle 4k+3.}$ 

Liczby pierwsze Mersenne’a

Nie wiadomo, czy istnieje nieskończenie wiele liczb pierwszych Mersenne’a. Obecnie poznano ich 51:

Lp.	n	Mn	Mn	Liczba cyfr w Mn	Data odkrycia	Odkrywca
1.	2	${\displaystyle 2^{2}-1}$	3	1
2.	3	${\displaystyle 2^{3}-1}$	7	1
3.	5	${\displaystyle 2^{5}-1}$	31	2
4.	7	${\displaystyle 2^{7}-1}$	127	3
5.	13	${\displaystyle 2^{13}-1}$	8191	4	1456	nieznany
6.	17	${\displaystyle 2^{17}-1}$	131071	6	1588	Pietro Cataldi(inne języki)
7.	19	${\displaystyle 2^{19}-1}$	524287	6	1588	Pietro Cataldi
8.	31	${\displaystyle 2^{31}-1}$	2147483647	10	1772	Leonhard Euler
9.	61	${\displaystyle 2^{61}-1}$	2305843009213693951	19	1883	Iwan Perwuszin(inne języki)
10.	89	${\displaystyle 2^{89}-1}$	618970019642690137449562111	27	1911	Ralph Ernest Powers(inne języki)
11.	107	${\displaystyle 2^{107}-1}$	162259276829213363391578010288127	33	1914	Ralph Ernest Powers
12.	127	${\displaystyle 2^{127}-1}$	170141183460469231731687303715884105727	39	10 czerwca 1876	Édouard Lucas
13.	521	${\displaystyle 2^{521}-1}$	68647976601306097149...12574028291115057151	157	30 stycznia 1952	Raphael Mitchel Robinson(inne języki)
14.	607	${\displaystyle 2^{607}-1}$	53113799281676709868...70835393219031728127	183	30 stycznia 1952	Raphael Mitchel Robinson
15.	1279	${\displaystyle 2^{1279}-1}$	10407932194664399081...20710555703168729087	386	25 czerwca 1952	Raphael Mitchel Robinson
16.	2 203	${\displaystyle 2^{2203}-1}$	14759799152141802350...50419497686697771007	664	7 października 1952	Raphael Mitchel Robinson
17.	2 281	${\displaystyle 2^{2281}-1}$	44608755718375842957...64133172418132836351	687	9 października 1952	Raphael Mitchel Robinson
18.	3 217	${\displaystyle 2^{3217}-1}$	25911708601320262777...46160677362909315071	969	8 września 1957	Hans Riesel(inne języki)
19.	4 253	${\displaystyle 2^{4253}-1}$	19079700752443907380...76034687815350484991	1 281	3 listopada 1961	Alexander Hurwitz
20.	4 423	${\displaystyle 2^{4423}-1}$	28554254222827961390...10231057902608580607	1 332	3 listopada 1961	Alexander Hurwitz
21.	9 689	${\displaystyle 2^{9689}-1}$	47822027880546120295...18992696826225754111	2 917	11 maja 1963	Donald Bruce Gillies(inne języki)
22.	9 941	${\displaystyle 2^{9941}-1}$	34608828249085121524...19426224883789463551	2 993	16 maja 1963	Donald Bruce Gillies
23.	11 213	${\displaystyle 2^{11213}-1}$	28141120136973731333...67391476087696392191	3 376	2 czerwca 1963	Donald Bruce Gillies
24.	19 937	${\displaystyle 2^{19937}-1}$	43154247973881626480...36741539030968041471	6 002	4 marca 1971	Bryant Tuckerman(inne języki)
25.	21 701	${\displaystyle 2^{21701}-1}$	44867916611904333479...57410828353511882751	6 533	30 października 1978	Landon Curt Noll(inne języki) i Laura Nickel
26.	23 209	${\displaystyle 2^{23209}-1}$	40287411577898877818...36743355523779264511	6 987	9 lutego 1979	Landon Curt Noll
27.	44 497	${\displaystyle 2^{44497}-1}$	85450982430363380319...44867686961011228671	13 395	8 kwietnia 1979	Harry Lewis Nelson(inne języki) i David Slowinski(inne języki)
28.	86 243	${\displaystyle 2^{86243}-1}$	53692799550275632152...99857021709433438207	25 962	25 września 1982	David Slowinski
29.	110 503	${\displaystyle 2^{110503}-1}$	52192831334175505976...69951621083465515007	33 265	28 stycznia 1988	Walt Colquitt i Luke Welsh
30.	132 049	${\displaystyle 2^{132049}-1}$	51274027626932072381...52138578455730061311	39 751	19 września 1983	David Slowinski
31.	216 091	${\displaystyle 2^{216091}-1}$	74609310306466134368...91336204103815528447	65 050	6 września 1985	David Slowinski
32.	756 839	${\displaystyle 2^{756839}-1}$	17413590682008709732...02603793328544677887	227 832	19 lutego 1992	David Slowinski(inne języki) i Paul Gage
33.	859 433	${\displaystyle 2^{859433}-1}$	12949812560420764966...02414267243500142591	258 716	10 stycznia 1994	David Slowinski i Paul Gage
34.	1 257 787	${\displaystyle 2^{1257787}-1}$	41224577362142867472...31257188976089366527	378 632	3 września 1996	David Slowinski i Paul Gage
35.	1 398 269	${\displaystyle 2^{1398269}-1}$	81471756441257307514...85532025868451315711	420 921	13 listopada 1996	GIMPS / Joel Armengaud
36.	2 976 221	${\displaystyle 2^{2976221}-1}$	62334007624857864988...76506256743729201151	895 932	24 sierpnia 1997	GIMPS / Gordon Spence
37.	3 021 377	${\displaystyle 2^{3021377}-1}$	12741168303009336743...25422631973024694271	909 526	27 stycznia 1998	GIMPS / Roland Clarkson
38.	6 972 593	${\displaystyle 2^{6972593}-1}$	43707574412708137883...35366526142924193791	2 098 960	1 czerwca 1999	GIMPS / Nayan Hajratwala
39.	13 466 917	${\displaystyle 2^{13466917}-1}$	92494773800670132224...30073855470256259071	4 053 946	14 listopada 2001	GIMPS / Michael Cameron
40.	20 996 011	${\displaystyle 2^{20996011}-1}$	12597689545033010502...94714065762855682047	6 320 430	17 listopada 2003	GIMPS / Michael Shafer
41.	24 036 583	${\displaystyle 2^{24036583}-1}$	29941042940415717208...67436921882733969407	7 235 733	15 maja 2004	GIMPS / Josh Findley
42.	25 964 951	${\displaystyle 2^{25964951}-1}$	12216463006127794810...98933257280577077247	7 816 230	18 lutego 2005	GIMPS / Martin Nowak
43.	30 402 457	${\displaystyle 2^{30402457}-1}$	31541647561884608093...11134297411652943871	9 152 052	15 grudnia 2005	GIMPS / Curtis Cooper i Steven Boone
44.	32 582 657	${\displaystyle 2^{32582657}-1}$	12457502601536945540...11752880154053967871	9 808 358	4 września 2006	GIMPS / Curtis Cooper i Steven Boone
45.	37 156 667	${\displaystyle 2^{37156667}-1}$	20225440689097733553...21340265022308220927	11 185 272	6 września 2008	GIMPS / Hans-Michael Elvenich
46.	42 643 801	${\displaystyle 2^{42643801}-1}$	16987351645274162247...84101954765562314751	12 837 064	4 czerwca 2009	GIMPS / Odd Magnar Strindmo
47.	43 112 609	${\displaystyle 2^{43112609}-1}$	31647026933025592314...80022181166697152511	12 978 189	23 sierpnia 2008	GIMPS / Edson Smith
48.	57 885 161	${\displaystyle 2^{57885161}-1}$	58188726623224644217...46141988071724285951	17 425 170	25 stycznia 2013	GIMPS / Curtis Cooper
49.*	74 207 281	${\displaystyle 2^{74207281}-1}$	30037641808460618205...87010073391086436351	22 338 618	7 stycznia 2016	GIMPS / Curtis Cooper
50.*	77 232 917	${\displaystyle 2^{77232917}-1}$	46733318335923109998...82730618069762179071	23 249 425	26 grudnia 2017	GIMPS / Jonathan Pace
51.*	82 589 933	${\displaystyle 2^{82589933}-1}$	14889444574204132554...37951210325217902591	24 862 048	7 grudnia 2018	GIMPS / Patrick Laroche

^* Październik 2021: Numeracja tymczasowa. Nie wiadomo czy między liczbami M57885161 i M82589933 nie ma innych jeszcze nieodkrytych liczb pierwszych Mersenne’a.

Test Lucasa-Lehmera

Pierwszość liczb Mersenne’a sprawdza się za pomocą testu Lucasa-Lehmera:

Przyjmijmy

S₁ = 4

i następnie

S_k = S_k−1² −2

Liczba M_p jest liczbą pierwszą wtedy i tylko wtedy, gdy:

S_p−1 ≡ 0 mod M_p.

Przykład zastosowania testu Lucasa: Rozważmy M₇ = 127

• S₁ = 4
• S₂ = 4² − 2 = 14
• S₃ = 14² − 2 = 194 ≡ 67 (mod 127)
• S₄ = 67² − 2 = 4487 ≡ 42 (mod 127)
• S₅ = 42² − 2 = 1762 ≡ 111 (mod 127)
• S₆ = 111² − 2 = 12319 ≡ 0 (mod 127)

liczba M₇ = 2⁷−1 = 127 jest liczbą pierwszą.

Największą obecnie znaną liczbą pierwszą Mersenne’a jest ${\displaystyle 2^{82589933}-1.}$  Odkrył ją 7 grudnia 2018 roku Patrick Laroche w ramach projektu GIMPS. Do jej zapisania w układzie dziesiętnym potrzeba 24 862 048 cyfr. Współcześnie poszukiwaniem liczb pierwszych Mersenne’a i rozkładaniem liczb złożonych na czynniki pierwsze zajmują się projekty obliczeń rozproszonych. Czołowym z nich jest właśnie GIMPS, do którego należy odkrycie ostatnich największych znanych liczb pierwszych.

Ta sekcja od 2018-05 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.

Liczby Mersenne’a są związane z odnajdywaniem kolejnych liczb doskonałych, ponieważ występują we wzorze, który je generuje: ${\displaystyle 2^{n-1}\cdot (2^{n}-1),}$  gdzie wyrażenie ${\displaystyle 2^{n}-1}$  to liczba pierwsza Mersenne’a ${\displaystyle M_{n}}$ .

Twierdzenie: Liczba Mersenne’a ${\displaystyle 2^{p}-1}$  jest złożona i podzielna przez ${\displaystyle q:=2p+1}$  dla dowolnej liczby pierwszej Germain ${\displaystyle p\equiv -1\!\!\!\!{\pmod {4}}.}$ 

Dowód: Na mocy twierdzenia o wzajemności kwadratowej, kongruencja ${\displaystyle x^{2}\equiv 2\!\!\!\!{\pmod {q}}}$  ma rozwiązanie dla liczby pierwszej nieparzystej ${\displaystyle q}$  wtedy i tylko wtedy, gdy ${\displaystyle q\equiv 1{\mbox{ lub }}-1\!\!\!\!{\pmod {8}}.}$ 

Niech ${\displaystyle p\equiv -1\!\!\!\!{\pmod {4}}}$  będzie liczbą pierwszą Germain, czyli ${\displaystyle p=4a-1}$  jest pierwsze, oraz ${\displaystyle q:=2p+1}$  jest liczbą pierwszą. Wtedy ${\displaystyle q=8a-1,}$  więc istnieje liczba całkowita ${\displaystyle r}$  taka, że ${\displaystyle r^{2}\equiv 2\!\!\!\!{\pmod {q}}.}$  Zatem na mocy Małego Twierdzenia Fermata: ${\displaystyle 2^{p}-1=r^{q-1}-1\equiv 0\!\!\!\!{\pmod {q}}.}$ 

Przykłady: ${\displaystyle p=11,\ 23,\ 83.}$ 

• The Great Internet Mersenne Prime Search (GIMPS) (ang.)
• Eric W.E.W. Weisstein Eric W.E.W., Mersenne Prime, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Eric W.E.W. Weisstein Eric W.E.W., Perfect Number, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Liczby pierwsze Mersenne’a (ang.)