Liczby Mersenne'a

Liczby Mersenne'a – liczby postaci $2^p - 1$, gdzie $p$ 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ą.

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

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ż 2¹¹−1 = 23·89.

Liczby złożone Mersenne'a

Istnieje nieskończenie wiele liczb złożonych Mersenne'a. Ich przykładami są:

$2^{11} -1 = 2047 = 23 \cdot 89$

$2^{23} -1 = 8388607=47 \cdot 178481$

$2^{29} -1 = 536870911=233 \cdot 2304167=233 \cdot 1103 \cdot 2089$

$2^{37} -1 = 137438953471=223 \cdot 616318177$

$2^{43} -1 = 8796093022207=431 \cdot 20408568497$

$2^{47} -1 = 140737488355327=2351 \cdot 4513 \cdot 13264529$

$2^{83} -1 = 167 \cdot 57912614113275649087721$

Liczby pierwsze Mersenne'a

Nie wiadomo, czy istnieje nieskończenie wiele liczb pierwszych Mersenne'a. Obecnie poznano ich 47:
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$

Test Lucasa-Lehmera

Pierwszość liczb Mersenne'a sprawdza się za pomocą testu Lucasa-Lehmera:

Przyjmijmy

S₁ = 4

i następnie

S_k = S_k−1² −2

Liczba M_p jest liczbą pierwszą wtedy i tylko wtedy gdy:

S_p−1 ≡ 0 mod M_p.

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

• S₁ = 4
• S₂ = 4² −2 = 14
• S₃ = 14² −2 = 194 ≡ 67 (mod 127)
• S₄ ≡ 67² −2 = 4487 ≡ 42 (mod 127)
• S₅ ≡ 42² −2 = 1762 ≡ 111 (mod 127)
• S₆ ≡ 111² −2 = 12319 ≡ 0 (mod 127)

liczba M₇ = 2⁷−1 = 127 jest liczbą pierwszą.

Największa liczba pierwsza Mersenne'a

Nie wiadomo, czy liczb pierwszych Mersenne'a jest nieskończenie wiele, a największą obecnie znaną liczbą pierwszą Mersenne'a jest $2^{43112609}-1$. Odkrył ją 23 sierpnia 2008 roku Edson Smith w ramach projektu GIMPS. Do jej zapisania w układzie dziesiętnym potrzeba 12 978 189 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 dwunastu największych znanych liczb pierwszych.

Liczby Mersenne'a a liczby doskonałe

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 Germaine

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.\;$

Linki zewnętrzne

• Strona GIMPS
• Polski projekt naukowy poszukujący liczb Mersenne'a
• [1]