Liczby Mersenne’a

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

Liczby Mersenne’aliczby pierwsze postaci , gdzie jest liczbą naturalną. Niektóre definicje wymagają ponadto, by liczba była liczbą pierwszą. 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ą.

Liczbę Mersenne’a M(p) można określić jako sumę p pierwszych wyrazów ciągu geometrycznego: , , , , ,...

Pierwszość liczb Mersenne’a[edytuj]

Liczby złożone Mersenne’a to liczby Mersenne’a M(p), które są złożone, gdy liczba p jest pierwsza (gdy p jest złożone, to M(p) jest zawsze złożone). Warunkiem koniecznym, ale nie wystarczającym, żeby liczba M(p) była pierwsza jest, by p było liczbą pierwszą. Przykładowo:

  • M(p) jest liczbą pierwszą dla p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607
  • M(p) jest liczbą złożoną dla p = 11, gdyż 211−1 = 23·89.

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

Istnieje nieskończenie wiele liczb złożonych Mersenne’a (o ile istnieje nieskończenie wiele liczb pierwszych Sophie Germain postaci 4k+3, a tego nie dowiedziono). Ich przykładami są:

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]