Liczby Mersenne'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Liczby Mersenne'aliczby postaci 2^p - 1, gdzie p jest liczbą naturalną. Niektóre definicje wymagają ponadto, by liczba p była liczbą pierwszą. 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ą.

Liczbę Mersenne'a M(p) można określić jako sumę p pierwszych wyrazów ciągu geometrycznego: 2^0, 2^1, 2^2, 2^3, 2^4,...

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

Liczby złożone Mersenne'a to liczby Mersenne'a M(p), które są złożone, gdy liczba p jest pierwsza (gdy p jest złożone, to M(p) jest zawsze złożone). Warunkiem koniecznym, ale nie wystarczającym, żeby liczba M(p) była pierwsza jest, by p było liczbą pierwszą. Przykładowo:

  • M(p) jest liczbą pierwszą dla p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607
  • M(p) jest liczbą złożoną dla p = 11, gdyż 211−1 = 23·89.

Liczby złożone Mersenne'a[edytuj | edytuj kod]

Istnieje nieskończenie wiele liczb złożonych Mersenne'a (o ile istnieje nieskończenie wiele liczb pierwszych Sophie Germain postaci 4k+3, a tego nie dowiedziono). 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^{43} -1 = 8796093022207=431 \cdot 9719 \cdot 2099863
2^{47} -1 = 140737488355327=2351 \cdot 4513 \cdot 13264529
2^{83} -1 = 9671406556917033397649407 = 167 \cdot 57912614113275649087721

Liczby pierwsze Mersenne'a[edytuj | edytuj kod]

Nie wiadomo, czy istnieje nieskończenie wiele liczb pierwszych Mersenne'a. Obecnie poznano ich 48:

  1. 2^2-1
  2. 2^3-1
  3. 2^5-1
  4. 2^7-1
  5. 2^{13}-1
  6. 2^{17}-1
  7. 2^{19}-1
  8. 2^{31}-1
  9. 2^{61}-1
  10. 2^{89}-1
  11. 2^{107}-1
  12. 2^{127}-1
  13. 2^{521}-1
  14. 2^{607}-1
  15. 2^{1279}-1
  16. 2^{2203}-1
  17. 2^{2281}-1
  18. 2^{3217}-1
  19. 2^{4253}-1
  20. 2^{4423}-1
  21. 2^{9689}-1
  22. 2^{9941}-1
  23. 2^{11213}-1
  24. 2^{19937}-1
  25. 2^{21701}-1
  26. 2^{23209}-1
  27. 2^{44497}-1
  28. 2^{86243}-1
  29. 2^{110503}-1
  30. 2^{132049}-1
  31. 2^{216091}-1
  32. 2^{756839}-1
  33. 2^{859433}-1
  34. 2^{1257787}-1
  35. 2^{1398269}-1
  36. 2^{2976221}-1
  37. 2^{3021377}-1
  38. 2^{6972593}-1
  39. 2^{13466917}-1
  40. 2^{20996011}-1
  41. 2^{24036583}-1
  42. 2^{25964951}-1
  43. 2^{30402457}-1
  44. 2^{32582657}-1
  45. 2^{37156667}-1
  46. 2^{42643801}-1
  47. 2^{43112609}-1
  48. 2^{57885161}-1[1][2]

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]

Nie wiadomo, czy liczb pierwszych Mersenne'a jest nieskończenie wiele, a największą obecnie znaną liczbą pierwszą Mersenne'a jest 2^{57885161}-1. Odkrył ją 25 stycznia 2013 roku Curtis Cooper[3] w ramach projektu GIMPS[2]. Do jej zapisania w układzie dziesiętnym potrzeba 17 425 170 cyfr[2]. 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 dwunastu największych znanych liczb pierwszych.

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: 2^{n-1} \cdot (2^{n}-1). Dzięki odkryciu liczby pierwszej Mersenne'a 2^{43112609}-1, odkryto nową liczbę doskonałą: 2^{43112608} \cdot \left(2^{43112609}-1\right).

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

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 \pmod 4\;.

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

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

Przykłady: p = 11,\ 23,\ 83.\;

Przypisy

Linki zewnętrzne[edytuj | edytuj kod]