Liczby Mersenne’a
Liczby Mersenne’a – liczby postaci gdzie 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 jest równa sumie ciągu geometrycznego
Pierwszość liczb Mersenne’a
Warunkiem koniecznym, żeby liczba była pierwsza jest, by było liczbą pierwszą.
Rzeczywiście, niech będzie liczbą złożoną, gdzie są liczbami naturalnymi. Wówczas
również jest złożona.
Pierwszość wskaźnika nie jest jednak wystarczająca dla pierwszości liczby np.:
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ą:
Hipoteza byłaby prawdziwa, gdyby okazało się, że istnieje nieskończenie wiele liczb pierwszych Germain mających postać
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 | 3 | 1 | |||
2. | 3 | 7 | 1 | |||
3. | 5 | 31 | 2 | |||
4. | 7 | 127 | 3 | |||
5. | 13 | 8191 | 4 | 1456 | nieznany | |
6. | 17 | 131071 | 6 | 1588 | Pietro Cataldi(inne języki) | |
7. | 19 | 524287 | 6 | 1588 | Pietro Cataldi | |
8. | 31 | 2147483647 | 10 | 1772 | Leonhard Euler | |
9. | 61 | 2305843009213693951 | 19 | 1883 | Iwan Perwuszin(inne języki) | |
10. | 89 | 618970019642690137449562111 | 27 | 1911 | Ralph Ernest Powers(inne języki) | |
11. | 107 | 162259276829213363391578010288127 | 33 | 1914 | Ralph Ernest Powers | |
12. | 127 | 170141183460469231731687303715884105727 | 39 | 10 czerwca 1876 | Édouard Lucas | |
13. | 521 | 68647976601306097149...12574028291115057151 | 157 | 30 stycznia 1952 | Raphael Mitchel Robinson(inne języki) | |
14. | 607 | 53113799281676709868...70835393219031728127 | 183 | 30 stycznia 1952 | Raphael Mitchel Robinson | |
15. | 1279 | 10407932194664399081...20710555703168729087 | 386 | 25 czerwca 1952 | Raphael Mitchel Robinson | |
16. | 2 203 | 14759799152141802350...50419497686697771007 | 664 | 7 października 1952 | Raphael Mitchel Robinson | |
17. | 2 281 | 44608755718375842957...64133172418132836351 | 687 | 9 października 1952 | Raphael Mitchel Robinson | |
18. | 3 217 | 25911708601320262777...46160677362909315071 | 969 | 8 września 1957 | Hans Riesel(inne języki) | |
19. | 4 253 | 19079700752443907380...76034687815350484991 | 1 281 | 3 listopada 1961 | Alexander Hurwitz | |
20. | 4 423 | 28554254222827961390...10231057902608580607 | 1 332 | 3 listopada 1961 | Alexander Hurwitz | |
21. | 9 689 | 47822027880546120295...18992696826225754111 | 2 917 | 11 maja 1963 | Donald Bruce Gillies(inne języki) | |
22. | 9 941 | 34608828249085121524...19426224883789463551 | 2 993 | 16 maja 1963 | Donald Bruce Gillies | |
23. | 11 213 | 28141120136973731333...67391476087696392191 | 3 376 | 2 czerwca 1963 | Donald Bruce Gillies | |
24. | 19 937 | 43154247973881626480...36741539030968041471 | 6 002 | 4 marca 1971 | Bryant Tuckerman(inne języki) | |
25. | 21 701 | 44867916611904333479...57410828353511882751 | 6 533 | 30 października 1978 | Landon Curt Noll(inne języki) i Laura Nickel | |
26. | 23 209 | 40287411577898877818...36743355523779264511 | 6 987 | 9 lutego 1979 | Landon Curt Noll | |
27. | 44 497 | 85450982430363380319...44867686961011228671 | 13 395 | 8 kwietnia 1979 | Harry Lewis Nelson(inne języki) i David Slowinski(inne języki) | |
28. | 86 243 | 53692799550275632152...99857021709433438207 | 25 962 | 25 września 1982 | David Slowinski | |
29. | 110 503 | 52192831334175505976...69951621083465515007 | 33 265 | 28 stycznia 1988 | Walt Colquitt i Luke Welsh | |
30. | 132 049 | 51274027626932072381...52138578455730061311 | 39 751 | 19 września 1983 | David Slowinski | |
31. | 216 091 | 74609310306466134368...91336204103815528447 | 65 050 | 6 września 1985 | David Slowinski | |
32. | 756 839 | 17413590682008709732...02603793328544677887 | 227 832 | 19 lutego 1992 | David Slowinski(inne języki) i Paul Gage | |
33. | 859 433 | 12949812560420764966...02414267243500142591 | 258 716 | 10 stycznia 1994 | David Slowinski i Paul Gage | |
34. | 1 257 787 | 41224577362142867472...31257188976089366527 | 378 632 | 3 września 1996 | David Slowinski i Paul Gage | |
35. | 1 398 269 | 81471756441257307514...85532025868451315711 | 420 921 | 13 listopada 1996 | GIMPS / Joel Armengaud | |
36. | 2 976 221 | 62334007624857864988...76506256743729201151 | 895 932 | 24 sierpnia 1997 | GIMPS / Gordon Spence | |
37. | 3 021 377 | 12741168303009336743...25422631973024694271 | 909 526 | 27 stycznia 1998 | GIMPS / Roland Clarkson | |
38. | 6 972 593 | 43707574412708137883...35366526142924193791 | 2 098 960 | 1 czerwca 1999 | GIMPS / Nayan Hajratwala | |
39. | 13 466 917 | 92494773800670132224...30073855470256259071 | 4 053 946 | 14 listopada 2001 | GIMPS / Michael Cameron | |
40. | 20 996 011 | 12597689545033010502...94714065762855682047 | 6 320 430 | 17 listopada 2003 | GIMPS / Michael Shafer | |
41. | 24 036 583 | 29941042940415717208...67436921882733969407 | 7 235 733 | 15 maja 2004 | GIMPS / Josh Findley | |
42. | 25 964 951 | 12216463006127794810...98933257280577077247 | 7 816 230 | 18 lutego 2005 | GIMPS / Martin Nowak | |
43. | 30 402 457 | 31541647561884608093...11134297411652943871 | 9 152 052 | 15 grudnia 2005 | GIMPS / Curtis Cooper i Steven Boone | |
44. | 32 582 657 | 12457502601536945540...11752880154053967871 | 9 808 358 | 4 września 2006 | GIMPS / Curtis Cooper i Steven Boone | |
45. | 37 156 667 | 20225440689097733553...21340265022308220927 | 11 185 272 | 6 września 2008 | GIMPS / Hans-Michael Elvenich | |
46. | 42 643 801 | 16987351645274162247...84101954765562314751 | 12 837 064 | 4 czerwca 2009 | GIMPS / Odd Magnar Strindmo | |
47. | 43 112 609 | 31647026933025592314...80022181166697152511 | 12 978 189 | 23 sierpnia 2008 | GIMPS / Edson Smith | |
48. | 57 885 161 | 58188726623224644217...46141988071724285951 | 17 425 170 | 25 stycznia 2013 | GIMPS / Curtis Cooper[3] | |
49.* | 74 207 281 | 30037641808460618205...87010073391086436351 | 22 338 618 | 7 stycznia 2016 | GIMPS / Curtis Cooper[4] | |
50.* | 77 232 917 | 46733318335923109998...82730618069762179071 | 23 249 425 | 26 grudnia 2017 | GIMPS / Jonathan Pace[5] | |
51.* | 82 589 933 | 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 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: gdzie wyrażenie to liczba pierwsza Mersenne’a [8].
Związek liczb złożonych Mersenne’a z liczbami pierwszymi Germain
Twierdzenie: Liczba Mersenne’a jest złożona i podzielna przez dla dowolnej liczby pierwszej Germain
Dowód: Na mocy twierdzenia o wzajemności kwadratowej, kongruencja ma rozwiązanie dla liczby pierwszej nieparzystej wtedy i tylko wtedy, gdy
Niech będzie liczbą pierwszą Germain, czyli jest pierwsze, oraz jest liczbą pierwszą. Wtedy więc istnieje liczba całkowita taka, że Zatem na mocy Małego Twierdzenia Fermata:
Przykłady:
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.).
- ↑ GIMPS Discovers 48th Mersenne Prime. [dostęp 2019-01-09]. (ang.).
- ↑ GIMPS Project Discovers Largest Known Prime Number: . [dostęp 2019-01-09]. (ang.).
- ↑ GIMPS Project Discovers Largest Known Prime Number: . [dostęp 2019-01-09]. (ang.).
- ↑ a b GIMPS Project Discovers Largest Known Prime Number: . [dostęp 2019-01-09]. (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.)
- p
- d
- e
zdefiniowane |
| ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
typy liczb pierwszych | |||||||||||||
inne typy liczb |
- p
- d
- e
pojęcia definiujące |
| ||||
---|---|---|---|---|---|
typy ciągów |
| ||||
przykłady ciągów liczb naturalnych | |||||
inne przykłady ciągów liczb | |||||
twierdzenia |
| ||||
powiązane pojęcia |
- PWN: 3939847
- Britannica: topic/Mersenne-prime