Liczby Mersenne’a

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’aEdytuj

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’aEdytuj

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’aEdytuj

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(ang.)
7. 19   524287 6 1588 Pietro Cataldi
8. 31   2147483647 10 1772 Leonhard Euler
9. 61   2305843009213693951 19 1883 Iwan Perwuszin(ang.)
10. 89   618970019642690137449562111 27 1911 Ralph Ernest Powers(ang.)
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(ang.)
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(ang.)
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(ang.)
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(ang.)
25. 21 701   44867916611904333479...57410828353511882751 6 533 30 października 1978 Landon Curt Noll(ang.) 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(ang.) i David Slowinski(ang.)
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(ang.) i Paul Gage(ang.)
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   14889444574204132554...37951210325217902591 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-LehmeraEdytuj

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’aEdytuj

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łeEdytuj

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 GermainEdytuj

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:  

PrzypisyEdytuj

Linki zewnętrzneEdytuj