Liczby Mersenne’a

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

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

Pierwszość liczb Mersenne’a

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

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

M n = 2 n − 1 = 2 a b − 1 = ( 2 a ) b − 1 b = ( 2 a − 1 ) ( 2 a ( b − 1 ) + 2 a ( b − 2 ) + 2 a ( b − 3 ) + … + 2 a ( b − b ) ) {\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 n {\displaystyle n} nie jest jednak wystarczająca dla pierwszości liczby M n , {\displaystyle M_{n},} np.:

M 11 = 2 11 − 1 = 23 ⋅ 89. {\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ą:

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

S1 = 4

i następnie

Sk = Sk−12 −2

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

Sp−1 ≡ 0 mod Mp.

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

  • S1 = 4
  • S2 = 42 − 2 = 14
  • S3 = 142 − 2 = 194 ≡ 67 (mod 127)
  • S4 = 672 − 2 = 4487 ≡ 42 (mod 127)
  • S5 = 422 − 2 = 1762 ≡ 111 (mod 127)
  • S6 = 1112 − 2 = 12319 ≡ 0 (mod 127)

liczba M7 = 27−1 = 127 jest liczbą pierwszą.

Największa liczba pierwsza Mersenne’a

Największą obecnie znaną liczbą pierwszą Mersenne’a jest 2 82589933 − 1. {\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

Wikipedia:Weryfikowalność
 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 ⋅ ( 2 n − 1 ) , {\displaystyle 2^{n-1}\cdot (2^{n}-1),} gdzie wyrażenie 2 n − 1 {\displaystyle 2^{n}-1} to liczba pierwsza Mersenne’a M n {\displaystyle M_{n}} [8].

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

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

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

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

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

Przypisy

  1. ↑ Liczby Mersenne’a, [w:] Encyklopedia PWN [dostęp 2021-09-15] .
  2. ↑ table of factors of small Mersenne numbers. planetmath.org. [dostęp 2022-06-03]. (ang.).
  3. ↑ GIMPS Discovers 48th Mersenne Prime. [dostęp 2019-01-09]. (ang.).
  4. ↑ GIMPS Project Discovers Largest Known Prime Number: 2 74207281 − 1 {\displaystyle 2^{74207281}-1} . [dostęp 2019-01-09]. (ang.).
  5. ↑ GIMPS Project Discovers Largest Known Prime Number: 2 77232917 − 1 {\displaystyle 2^{77232917}-1} . [dostęp 2019-01-09]. (ang.).
  6. ↑ a b GIMPS Project Discovers Largest Known Prime Number: 2 82589933 − 1 {\displaystyle 2^{82589933}-1} . [dostęp 2019-01-09]. (ang.).
  7. ↑ List of Known Mersenne Prime Numbers. [dostęp 2019-01-09]. (ang.).
  8. ↑ 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.).
  • publikacja w otwartym dostępie – możesz ją przeczytać Mersenne number (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-12].
  • Liczby pierwsze Mersenne’a (ang.)
  • p
  • d
  • e
Ciągi liczbowe
pojęcia
definiujące
ciągi ogólne
ciągi liczbowe
typy ciągów
ogólne
nieskończone
przykłady ciągów
liczb naturalnych
niemalejące
inne
inne przykłady
ciągów liczb
twierdzenia
o granicach
inne
powiązane pojęcia