ResponseEve, a responsive template by SiGa

Liczby Mersenne’a – liczby postaci ${\displaystyle M_{n}=2^{n}-1,}$ gdzie ${\displaystyle n}$ jest liczbą naturalną^[1]. 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}.}$

Pierwszość liczb Mersenne’a

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}$^[2]

${\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[3]
49.*	74 207 281	${\displaystyle 2^{74207281}-1}$	30037641808460618205...87010073391086436351	22 338 618	7 stycznia 2016	GIMPS / Curtis Cooper[4]
50.*	77 232 917	${\displaystyle 2^{77232917}-1}$	46733318335923109998...82730618069762179071	23 249 425	26 grudnia 2017	GIMPS / Jonathan Pace[5]
51.*	82 589 933	${\displaystyle 2^{82589933}-1}$	14889444574204132554...37951210325217902591	24 862 048	7 grudnia 2018	GIMPS / Patrick Laroche[6]

^* 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ększa liczba pierwsza Mersenne’a

Największą obecnie znaną liczbą pierwszą Mersenne’a jest ${\displaystyle 2^{82589933}-1.}$ Odkrył ją 7 grudnia 2018 roku Patrick Laroche^[6] 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^[7].

Liczby Mersenne’a a liczby doskonałe

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}}$^[8].

Związek liczb złożonych Mersenne’a z liczbami pierwszymi Germain

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.}$

Przypisy

Linki zewnętrzne

• 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.)