Liczby Mersenne’a

Z Wikipedii, wolnej encyklopedii
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 jest równa sumie ciągu geometrycznego

.

Pierwszość liczb Mersenne’a[edytuj]

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

Rzeczywiście, niech bedzie liczbą złożoną, gdzie są liczba naturalnymi. Wówczas

również jest złożona.

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

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ć .

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]