Liczby Mersenne’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Liczby Mersenne'a)
Skocz do: nawigacja, szukaj

Liczby Mersenne’a – liczby postaci , gdzie 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ą.

Liczba Mersenne’a M(p) jest równa sumie ciągu geometrycznego .

Pierwszość liczb Mersenne’a[edytuj]

Warunkiem koniecznym, żeby liczba M(p) była pierwsza jest, by p było liczbą pierwszą.

Rzeczywiście, niech , gdzie są liczba naturalnymi. Wówczas

Pierwszość wskaźnika p nie jest jednak wystarczająca dla pierwszości liczby M(p), np.:

M(11)=211−1 = 23·89.

Liczby złożone Mersenne’a[edytuj]

Nie wiadomo, czy istnieje nieskończenie wiele liczb złożonych Mersenne’a o wskaźnikach pierwszych. Ich przykładami są:

Hipoteza byłaby prawdziwa, gdyby okazało się, że istnieje nieskończenie wiele liczb pierwszych Sophie Germain mających postać 4k+3, ale tego nie dowiedziono do tej pory.

Liczby pierwsze Mersenne’a[edytuj]

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

  1. [1][2]
  2. [3]

Test Lucasa-Lehmera[edytuj]

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]

Nie wiadomo, czy liczb pierwszych Mersenne’a jest nieskończenie wiele, a największą obecnie znaną liczbą pierwszą Mersenne’a jest . Odkrył ją 7 stycznia 2016 roku Curtis Cooper[4] w ramach projektu GIMPS[2]. Do jej zapisania w układzie dziesiętnym potrzeba 22 338 618 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 piętnastu największych znanych liczb pierwszych[4].

Liczby Mersenne’a a liczby doskonałe[edytuj]

Liczby Mersenne’a są związane z odnajdywaniem kolejnych liczb doskonałych, ponieważ występują we wzorze, który je generuje: . Dzięki odkryciu liczby pierwszej Mersenne’a , odkryto nową liczbę doskonałą: .

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

Twierdzenie: Liczba Mersenne’a jest złożona i podzielna przez dla dowolnej liczby pierwszej Germain .

Dowód: Na mocy twierdzenia o wzajemności kwadratowej, kongruencja ma rozwiązanie dla liczby pierwszej nieparzystej wtedy i tylko wtedy, gdy

Niech będzie liczbą pierwszą Germain, czyli jest pierwsze, oraz jest liczbą pierwszą. Wtedy więc istnieje liczba całkowita taka, że Zatem na mocy Małego Twierdzenia Fermata:

Przykłady:

Przypisy

Linki zewnętrzne[edytuj]