Liczby Mersenne’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Liczby Mersenne'a)
Przejdź do nawigacji Przejdź do wyszukiwania

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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

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

Test Lucasa-Lehmera[edytuj | edytuj kod]

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 | edytuj kod]

Nie wiadomo, czy liczb pierwszych Mersenne’a jest nieskończenie wiele, a największą obecnie znaną liczbą pierwszą Mersenne’a jest . Odkrył ją 3 stycznia 2018 roku Jonathan Pace[3] w ramach projektu GIMPS[2]. Do jej zapisania w układzie dziesiętnym potrzeba 23 249 425 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 szesnastu największych znanych liczb pierwszych[3].

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

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łą: , która jest największą znaną nam liczbą doskonałą.

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

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[edytuj | edytuj kod]

  1. a b c The Largest Known Primes
  2. a b Krzysiek Dzieliński: Odkryto 48. liczbę pierwszą Mersenne’a. geekweek.pl, 2012-02-09. [dostęp 2012-02-09].
  3. a b c Mersenne Prime Discovery - 2^77232917-1 is Prime!, www.mersenne.org [dostęp 2018-01-06] (ang.).

Linki zewnętrzne[edytuj | edytuj kod]