Liczby Mersenne'a
Z Wikipedii
Spis treści |
[edytuj] Definicja
Liczby Mersenne'a to liczby określone wzorem 2p − 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 n = 11 otrzymujemy liczbę złożoną, gdyż 211-1 = 23x89.
[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 232582657-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 kolejnym liczb doskonałych, ponieważ występują we wzorze, który generuje liczby doskonałe: 
. Dzięki odkryciu liczby pierwszej Mersenne'a 232582657 − 1, odkryto nową liczbę doskonałą: 
.
[edytuj] Kilka liczb złożonych Mersenne'a
Liczba 283 − 1 jest podzielna przez 167.
[edytuj] Test Lucasa
Pierwszość liczb Mersenne'a sprawdza się za pomocą tzw. testu Lucasa:
przyjmijmy
- S1 = 4 i następnie
- Sk = Sk-12 -2
liczba Mp jest liczbą pierwszą wtedy i tylko wtedy gdy Sp-1 dzieli się przez Mp
[edytuj] Przykład zastosowania testu Lucasa część I
- S1 = 4
- S2 = 42 -2 = 14
- S3 = 142 -2 = 194
- S4 = 1942 -2 = 37634
liczba M5 = 31 jest liczbą pierwszą ponieważ 37634 / 31 = 1214
[edytuj] Przykład zastosowania testu Lucasa część II
liczby powstające w powyższym ciągu są na tyle duże, iż w praktyce operuje się resztą z dzielenia.
oto przykład rozważmy M7 = 127
- S1 = 4
- S2 = 42 -2 = 14
- S3 = 142 -2 = 194 i teraz 194 mod 127 = 67
- S4 = 672 -2 = 4487 i teraz 4487 mod 127 = 42
- S5 = 422 -2 = 1762 i teraz 1762 mod 127 = 111
- S6 = 1112 -2 = 12319 i teraz 12319 mod 127 = 0
liczba M7 = 127 jest liczbą pierwszą ponieważ 12319 / 127 = 97
[edytuj] Znane liczby pierwsze Mersenne'a
1. 22 − 1
2. 23 − 1
3. 25 − 1
4. 27 − 1
5. 213 − 1
6. 217 − 1
7. 219 − 1
8. 231 − 1
9. 261 − 1
10. 289 − 1
11. 2107 − 1
12. 2127 − 1
13. 2521 − 1
14. 2607 − 1
15. 21279 − 1
16. 22203 − 1
17. 22281 − 1
18. 23217 − 1
19. 24253 − 1
20. 24423 − 1
21. 29689 − 1
22. 29941 − 1
23. 211213 − 1
24. 219937 − 1
25. 221701 − 1
26. 223209 − 1
27. 244497 − 1
28. 286243 − 1
29. 2110503 − 1
30. 2132049 − 1
31. 2216091 − 1
32. 2756839 − 1
33. 2859433 − 1
34. 21257787 − 1
35. 21398269 − 1
36. 22976221 − 1
37. 23021377 − 1
38. 26972593 − 1
39. 213466917 − 1
40. 220996011 − 1
41. 224036583 − 1
42. 225964951 − 1
43. 230402457 − 1
44. 232582657 − 1
