Liczby Mersenne’a

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Liczby Mersenne’a – liczby postaci , gdzie 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 jest równa sumie ciągu geometrycznego

.

Pierwszość liczb Mersenne’a[edytuj | edytuj kod]

Warunkiem koniecznym, żeby liczba była pierwsza jest, by było liczbą pierwszą.

Rzeczywiście, niech bedzie liczbą złożoną, gdzie są liczba 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[edytuj | edytuj kod]

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 Sophie Germain mających postać .

Liczby pierwsze Mersenne’a[edytuj | edytuj kod]

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
7. 19 524287 6 1588 Pietro Cataldi
8. 31 2147483647 10 1772 Leonhard Euler
9. 61 2305843009213693951 19 1883 Iwan Perwuszin
10. 89 618970019642690137449562111 27 1911 Ralph Ernest Powers
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
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
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
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
25. 21 701 44867916611904333479...57410828353511882751 6 533 30 października 1978 Landon Curt Noll 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 i David Slowinski
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 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[1]
49.* 74 207 281 30037641808460618205...87010073391086436351 22 338 618 7 stycznia 2016 GIMPS / Curtis Cooper[2]
50.* 77 232 917 46733318335923109998...82730618069762179071 23 249 425 26 grudnia 2017 GIMPS / Jonathan Pace[3]
51.* 82 589 933 46733318335923109998...82730618069762179071 24 862 048 7 grudnia 2018 GIMPS / Patrick Laroche[4]

* Styczeń 2019: Numeracja tymczasowa. Nie wiadomo czy między liczbami M43112609 i M82589933 nie ma innych jeszcze nieodkrytych liczb pierwszych Mersenne'a.

Test Lucasa-Lehmera[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Największą obecnie znaną liczbą pierwszą Mersenne’a jest . Odkrył ją 7 grudnia 2018 roku Patrick Laroche[4] 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[5].

Liczby Mersenne’a a liczby doskonałe[edytuj | edytuj kod]

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 [6].

Związek liczb złożonych Mersenne’a z liczbami pierwszymi Germain[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]