Liczby Mersenne’a

Liczby Mersenne’a – liczby postaci $M_{n}=2^{n}-1,$ gdzie $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 $M_{n}$ jest równa sumie ciągu geometrycznego

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

Pierwszość liczb Mersenne’a

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

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

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 $n$ nie jest jednak wystarczająca dla pierwszości liczby $M_{n},$ np.:

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ą:

2^{11}-1=2047=23\cdot 89

2^{23}-1=8388607=47\cdot 178481

2^{29}-1=536870911=233\cdot 1103\cdot 2089

2^{37}-1=137438953471=223\cdot 616318177

2^{41}-1=2199023255551=13367\cdot 164511353

2^{43}-1=8796093022207=431\cdot 9719\cdot 2099863

2^{47}-1=140737488355327=2351\cdot 4513\cdot 13264529

2^{53}-1=9007199254740991=6361\cdot 69431\cdot 20394401

2^{59}-1=576460752303423487=179951\cdot 3203431780337

^[2]

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ć $4k+3.$

Liczby pierwsze Mersenne’a

Nie wiadomo, czy istnieje nieskończenie wiele liczb pierwszych Mersenne’a. Obecnie poznano ich 52^[3]:

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

^* Październik 2024: Numeracja tymczasowa. Nie wiadomo czy między liczbami M57885161 i M136279841 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 $2^{136279841}-1.$ Odkrył ją 12 października 2024 roku Luke Durant^[8] w ramach projektu GIMPS. Do jej zapisania w układzie dziesiętnym potrzeba 41 024 320 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^[9].

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: $2^{n-1}\cdot (2^{n}-1),$ gdzie wyrażenie $2^{n}-1$ to liczba pierwsza Mersenne’a $M_{n}$ ^[10].

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

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

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

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

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

Przypisy

↑ Liczby Mersenne’a, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-09-15] .
↑ table of factors of small Mersenne numbers. planetmath.org. [dostęp 2022-06-03]. (ang.).
↑ Mersenne Prime [online], mathworld.wolfram.com [dostęp 2024-10-21] (ang.).
↑ GIMPS Discovers 48th Mersenne Prime. [dostęp 2019-01-09]. (ang.).
↑ GIMPS Project Discovers Largest Known Prime Number: $2^{74207281}-1$ . [dostęp 2019-01-09]. (ang.).
↑ GIMPS Project Discovers Largest Known Prime Number: $2^{77232917}-1$ . [dostęp 2019-01-09]. (ang.).
↑ GIMPS Project Discovers Largest Known Prime Number: $2^{82589933}-1$ . mersenne.org, 2021-12-21. [dostęp 2019-01-09]. (ang.).
↑ ^a ^b GIMPS Discovers Largest Known Prime Number: $2^{136279841}-1$ . mersenne.org, 2024-10-21. [dostęp 2024-10-21]. (ang.).
↑ List of Known Mersenne Prime Numbers. [dostęp 2019-01-09]. (ang.).
↑ Włodzimierz Holsztyński: Liczby doskonałe. [dostęp 2019-01-09]. [zarchiwizowane z tego adresu (2019-01-10)]. (pol.).

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.).
Mersenne number (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-12].
Liczby pierwsze Mersenne’a (ang.)

[1] Liczby Mersenne’a, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-09-15] .

[2] table of factors of small Mersenne numbers. planetmath.org. [dostęp 2022-06-03]. (ang.).

[3] Mersenne Prime [online], mathworld.wolfram.com [dostęp 2024-10-21] (ang.).

[MP48-4] GIMPS Discovers 48th Mersenne Prime. [dostęp 2019-01-09]. (ang.).

[MP49-5] GIMPS Project Discovers Largest Known Prime Number: $2^{74207281}-1$ . [dostęp 2019-01-09]. (ang.).

[MP50-6] GIMPS Project Discovers Largest Known Prime Number: $2^{77232917}-1$ . [dostęp 2019-01-09]. (ang.).

[MP51-7] GIMPS Project Discovers Largest Known Prime Number: $2^{82589933}-1$ . mersenne.org, 2021-12-21. [dostęp 2019-01-09]. (ang.).

[MP52-8] GIMPS Discovers Largest Known Prime Number: $2^{136279841}-1$ . mersenne.org, 2024-10-21. [dostęp 2024-10-21]. (ang.).

[MP-9] List of Known Mersenne Prime Numbers. [dostęp 2019-01-09]. (ang.).

[LD-10] Włodzimierz Holsztyński: Liczby doskonałe. [dostęp 2019-01-09]. [zarchiwizowane z tego adresu (2019-01-10)]. (pol.).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]