Liczby Mersenne’a

Liczby Mersenne’a – liczby postaci $M_n=2^n-1,$ gdzie $n$ jest liczbą naturalną. 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+\dots +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)}+\dots +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 wykładnikach będących liczbami pierwszymi. 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^{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:

Lp.	n	Mn	Mn	Liczba cyfr w Mn	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	Szablon:Link-interwiki
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	Szablon:Link-interwiki
10.	89	$2^{89}-1$	618970019642690137449562111	27	1911	Szablon:Link-interwiki
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	Szablon:Link-interwiki
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	Szablon:Link-interwiki
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	Szablon:Link-interwiki
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	Szablon:Link-interwiki
25.	21 701	$2^{21701}-1$	44867916611904333479...57410828353511882751	6 533	30 października 1978	Szablon:Link-interwiki 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	Szablon:Link-interwiki i Szablon:Link-interwiki
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	Szablon:Link-interwiki 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 CooperSzablon:R
49.*	74 207 281	$2^{74207281}-1$	30037641808460618205...87010073391086436351	22 338 618	7 stycznia 2016	GIMPS / Curtis CooperSzablon:R
50.*	77 232 917	$2^{77232917}-1$	46733318335923109998...82730618069762179071	23 249 425	26 grudnia 2017	GIMPS / Jonathan PaceSzablon:R
51.*	82 589 933	$2^{82589933}-1$	14889444574204132554...37951210325217902591	24 862 048	7 grudnia 2018	GIMPS / Patrick LarocheSzablon:R
52.*	136 279 841	$2^{136279841}-1$	88169432750383326555...55076706219486871551	41 024 320	12 października 2024	GIMPS / Luke DurantSzablon:R

^* 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 DurantSzablon:R w ramach projektu GIMPS. Do jej zapisania w układzie dziesiętnym potrzeba Szablon:Nowrap 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 pierwszychSzablon:R.

Liczby Mersenne’a a liczby doskonałe

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$Szablon:R.

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(\mathrm{mod}4).$

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

Niech $p\equiv -1(\mathrm{mod}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(\mathrm{mod}q).$ Zatem na mocy Małego Twierdzenia Fermata: $2^p-1=r^{q-1}-1\equiv 0(\mathrm{mod}q).$

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

Linki zewnętrzne

• The Great Internet Mersenne Prime Search (GIMPS) Szablon:Lang
• Szablon:MathWorld
• Szablon:Otwarty dostęp Mersenne number Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-12].
• Liczby pierwsze Mersenne’a Szablon:Lang