Liczby Mersenne'a

Z Wikipedii

Spis treści 1 Definicja 2 Pierwszość liczb Mersenne'a 3 Największa liczba Mersenne'a 4 Liczby Mersenne'a a liczby doskonałe 5 Kilka liczb złożonych Mersenne'a 6 Test Lucasa 6.1 Przykład zastosowania testu Lucasa 7 Znane liczby pierwsze Mersenne'a 8 Zobacz też 9 Linki zewnętrzne

[edytuj] Definicja

Liczby Mersenne'a to liczby określone wzorem 2^p − 1 gdzie p jest liczbą pierwszą. Liczby Mersenne'a zostały tak nazwane na cześć francuskiego matematyka Marina Mersenne'a, który opublikował tablicę liczb pierwszych tego typu - niestety błędną.

[edytuj] Pierwszość liczb Mersenne'a

Niektóre z liczb Mersenne'a są liczbami pierwszymi, na przykład dla p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607,... Jednak dla p = 11 otrzymujemy liczbę złożoną, gdyż 2¹¹-1 = 23·89.

[edytuj] Największa liczba Mersenne'a

Nie wiadomo, czy liczb pierwszych Mersenne'a jest nieskończenie wiele, największą obecnie znaną liczbą pierwszą Mersenne'a jest 2^32582657-1. Odkryli ją 4 września 2006 roku S.Boone i C.Cooper w ramach projektu GIMPS. Do jej zapisania w układzie dziesiętnym potrzeba 9808358 cyfr. Współcześnie poszukiwaniem liczb pierwszych Mersenne'a i rozkładaniem liczb złożonych na czynniki pierwsze zajmują się rozmaite projekty obliczeń rozproszonych. Czołowym z nich jest właśnie GIMPS, do którego należy odkrycie ostatnich dziesięciu największych znanych liczb pierwszych. Electronic Frontier Foundation wyznaczyła nagrodę 100.000 dolarów za zidentyfikowanie liczby pierwszej mającej ponad 10 milionów cyfr.

[edytuj] 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 generuje liczby doskonałe: . Dzięki odkryciu liczby pierwszej Mersenne'a 2^32582657 − 1, odkryto nową liczbę doskonałą: .

[edytuj] Kilka liczb złożonych Mersenne'a

[edytuj] Test Lucasa

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

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.

[edytuj] 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ą.

[edytuj] Znane liczby pierwsze 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

[edytuj] Zobacz też

• Liczba pierwsza
• GIMPS

[edytuj] Linki zewnętrzne

• Strona GIMPS