Liczby Mersenne'a

W XVII wieku francuski mnich Marin Mersenne rozpatrywał możliwość istnienia liczb pierwszych postaci 2ⁿ - 1. Stwierdził, że 2ⁿ - 1 jest liczbą pierwszą dla n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 i nie jest nią dla żadnej inne wartości n mniejszej od 257. Przez następne dwa wieki nikt nie był wstanie tego potwierdzić ani zaprzeczyć. W 1876 r. E. Lucasowi udało się udowodnić, że 2¹²⁷ - 1 jest liczbą pierwszą i przez następnych siedem dekad była to największa liczba pierwsza. W tym czasie odkryto błędy w stwierdzeniu Mersenne'a, pomylił się w przypadku liczb 67 i 257, a pominął liczby 61, 89 i 107, które podstawione w miejsce n dają liczby pierwsze.

Liczby postaci M_n = 2ⁿ - 1, gdzie n jest liczbą naturalną nazywamy liczbami Mersenne'a.

Liczby Mersenne'a można określić także jako sumę n pierwszych wyrazów postępu geometrycznego 2⁰, 2¹, 2², 2³, ...
Mamy więc M₁ = 1, M₂ = 3, M₃ = 7, M₄ = 15, M₅ = 31, M₆ = 63, ...
Wiadomo, że jeżeli n jest liczbą złożoną, to liczba M_n jest także liczbą złożoną. Prawdziwe jest także stwierdzenie, że jeżeli liczba M_n jest liczbą pierwszą, to liczba n musi być pierwszą, ale niekoniecznie na odwrót.

Zagadnienie polega na tym, żeby rozstrzygnąć, czy dana liczba Mersenne'a jest pierwsza, a jeżeli nie jest, żeby znaleźć jej dzielniki. Wynik dotyczący dzielników sformułował Leonhard Euler w 1750 r.:

Jeżeli n > 3 jest liczbą pierwszą, n ≡ 3 (mod 4), to liczba 2n + 1 dzieli M_n wtedy i tylko wtedy, gdy 2n + 1 jest liczbą pierwszą, wówczas M_n jest liczbą złożoną.

Liczby pierwsze Mersenne'a M_p, gdzie p jest liczbą pierwszą oraz p ≤ 127, zostały odkryte przed erą komputerów. Pierwszą próbę szukania liczb pierwszych Mersenne'a przy użyciu komputera podjął w 1951 r. A. Turing, ale nie odniósł sukcesu. Obecnie znane są metody umożliwiające sprawdzenie czy liczba 2^p - 1, jest pierwsza czy też złożona, jedną z metod polega na obliczaniu wyrazów pewnego ciągu rekurencyjnego podanego przez E. Lucasa i D.H. Lehmera:

Liczba M_p, gdzie p jest liczbą pierwszą nieparzystą, wtedy i tylko wtedy jest pierwszą, gdy liczba M_p jest dzielnikiem (p - 1)-go wyrazu ciągu a_n określonego jako:
a₁ = 4
$a_{n + 1} = a_{n}^{2} - 2$ , dla n = 1, 2, ...

Metody tej w 1952 roku użył R. M. Robinson i znalazł liczby pierwsze Mersenne'a M₅₂₁ i M₆₀₇. Były to pierwsze tego rodzaju odkrycia dokonane za pomocą komputera. Obecnie największą liczbą Mersenne'a jest 2^32582657 - 1 znaleziona w 2006 roku i licząca 9 808 358 cyfr. Mając jednak do dyspozycji coraz to mocniejsze jednostki obliczeniowe, w każdej chwili możemy spodziewać się odkrycia nowej liczby pierwszej Mersenne'a. Prawdopodomnie nie dla wszystkich liczb pierwszych p mniejszych od rekordowej zbadano czy liczba M_p jest pierwsza, może się więc zdarzyć, że kolejna znaleziona liczba pierwsza Mersenne'a będzie mniejsza.

Wykaz liczb pierwszych Mersenne'a

1. 2² - 1
2. 2³ - 1
3. 2⁵ - 1
4. 2⁷ - 1
5. 2¹³ - 1
6. 2¹⁷ - 1
7. 2¹⁹ - 1
8. 2³¹ - 1
9. 2⁶¹ - 1
10. 2⁸⁹ - 1
11. 2¹⁰⁷ - 1
12. 2¹²⁷ - 1
13. 2⁵²¹ - 1
14. 2⁶⁰⁷ - 1
15. 2¹²⁷⁹ - 1
16. 2²²⁰³ - 1
17. 2²²⁸¹ - 1
18. 2³²¹⁷ - 1
19. 2⁴²⁵³ - 1
20. 2⁴⁴²³ - 1
21. 2⁹⁶⁸⁹ - 1
22. 2⁹⁹⁴¹ - 1
23. 2¹¹²¹³ - 1
24. 2¹⁹⁹³⁷ - 1
25. 2²¹⁷⁰¹ - 1
26. 2²³²⁰⁹ - 1
27. 2⁴⁴⁴⁹⁷ - 1
28. 2⁸⁶²⁴³ - 1
29. 2¹¹⁰⁵⁰³ - 1
30. 2¹³²⁰⁴⁹ - 1
31. 2²¹⁶⁰⁹¹ - 1
32. 2⁷⁵⁶⁸³⁹ - 1
33. 2⁸⁵⁹⁴³³ - 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^43112609 - 1
46. 2^37156667 - 1

Liczby Mersenne'a są związane z odnajdywaniem kolejnych liczb doskonałych, ponieważ występują we wzorze, który generuje liczby doskonałe. Odkryciu nowej liczby pierwszej Mersenne'a towarzyszy więc odkrycie nowej liczby doskonałej.