Liczby Mersenne’a

Liczby Mersenne’a – liczby postaci ${\displaystyle M_{n}=2^{n}-1,}$ gdzie ${\displaystyle n}$ jest liczbą naturalną^[1]. 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 ${\displaystyle M_{n}}$ jest równa sumie ciągu geometrycznego

${\displaystyle 2^{0}+2^{1}+2^{2}+2^{3}+\dots +2^{n-1}.}$

Pierwszość liczb Mersenne’a

Warunkiem koniecznym, żeby liczba ${\displaystyle M_{n}}$ była pierwsza jest, by ${\displaystyle n}$ było liczbą pierwszą.

Rzeczywiście, niech ${\displaystyle n=ab}$ będzie liczbą złożoną, gdzie ${\displaystyle a,b>1}$ są liczbami naturalnymi. Wówczas

${\displaystyle M_{n}=2^{n}-1=2^{ab}-1=(2^{a})^{b}-1^{b}=(2^{a}-1)(2^{a(b-1)}+2^{a(b-2)}+2^{a(b-3)}+\dots +2^{a(b-b)})}$

również jest złożona.

Pierwszość wskaźnika ${\displaystyle n}$ nie jest jednak wystarczająca dla pierwszości liczby ${\displaystyle M_{n},}$ np.:

${\displaystyle M_{11}=2^{11}-1=23\cdot 89.}$

Liczby złożone Mersenne’a

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

${\displaystyle 2^{11}-1=2047=23\cdot 89}$

${\displaystyle 2^{23}-1=8388607=47\cdot 178481}$

${\displaystyle 2^{29}-1=536870911=233\cdot 1103\cdot 2089}$

${\displaystyle 2^{37}-1=137438953471=223\cdot 616318177}$

${\displaystyle 2^{43}-1=8796093022207=431\cdot 9719\cdot 2099863}$

${\displaystyle 2^{47}-1=140737488355327=2351\cdot 4513\cdot 13264529}$

${\displaystyle 2^{53}-1=9007199254740991=6361\cdot 69431\cdot 20394401}$

${\displaystyle 2^{59}-1=576460752303423487=179951\cdot 3203431780337}$^[2]

${\displaystyle 2^{83}-1=9671406556917033397649407=167\cdot 57912614113275649087721}$

Hipoteza byłaby prawdziwa, gdyby okazało się, że istnieje nieskończenie wiele liczb pierwszych Germain mających postać ${\displaystyle 4k+3.}$

Liczby pierwsze Mersenne’a

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

^* Październik 2021: Numeracja tymczasowa. Nie wiadomo czy między liczbami M57885161 i M82589933 nie ma innych jeszcze nieodkrytych liczb pierwszych Mersenne’a.

Test Lucasa-Lehmera

Pierwszość liczb Mersenne’a sprawdza się za pomocą testu Lucasa-Lehmera:

Przyjmijmy

S₁ = 4

i następnie

S_k = S_k−1² −2

Liczba M_p jest liczbą pierwszą wtedy i tylko wtedy, gdy:

S_p−1 ≡ 0 mod M_p.

Przykład zastosowania testu Lucasa: Rozważmy M₇ = 127

• S₁ = 4
• S₂ = 4² − 2 = 14
• S₃ = 14² − 2 = 194 ≡ 67 (mod 127)
• S₄ = 67² − 2 = 4487 ≡ 42 (mod 127)
• S₅ = 42² − 2 = 1762 ≡ 111 (mod 127)
• S₆ = 111² − 2 = 12319 ≡ 0 (mod 127)

liczba M₇ = 2⁷−1 = 127 jest liczbą pierwszą.

Największa liczba pierwsza Mersenne’a

Największą obecnie znaną liczbą pierwszą Mersenne’a jest ${\displaystyle 2^{82589933}-1.}$ Odkrył ją 7 grudnia 2018 roku Patrick Laroche^[6] w ramach projektu GIMPS. Do jej zapisania w układzie dziesiętnym potrzeba 24 862 048 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 największych znanych liczb pierwszych^[7].

Liczby Mersenne’a a liczby doskonałe

Ta sekcja od 2018-05 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.

Liczby Mersenne’a są związane z odnajdywaniem kolejnych liczb doskonałych, ponieważ występują we wzorze, który je generuje: ${\displaystyle 2^{n-1}\cdot (2^{n}-1),}$ gdzie wyrażenie ${\displaystyle 2^{n}-1}$ to liczba pierwsza Mersenne’a ${\displaystyle M_{n}}$^[8].

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

Twierdzenie: Liczba Mersenne’a ${\displaystyle 2^{p}-1}$ jest złożona i podzielna przez ${\displaystyle q:=2p+1}$ dla dowolnej liczby pierwszej Germain ${\displaystyle p\equiv -1\!\!\!\!{\pmod {4}}.}$

Dowód: Na mocy twierdzenia o wzajemności kwadratowej, kongruencja ${\displaystyle x^{2}\equiv 2\!\!\!\!{\pmod {q}}}$ ma rozwiązanie dla liczby pierwszej nieparzystej ${\displaystyle q}$ wtedy i tylko wtedy, gdy ${\displaystyle q\equiv 1{\mbox{ lub }}-1\!\!\!\!{\pmod {8}}.}$

Niech ${\displaystyle p\equiv -1\!\!\!\!{\pmod {4}}}$ będzie liczbą pierwszą Germain, czyli ${\displaystyle p=4a-1}$ jest pierwsze, oraz ${\displaystyle q:=2p+1}$ jest liczbą pierwszą. Wtedy ${\displaystyle q=8a-1,}$ więc istnieje liczba całkowita ${\displaystyle r}$ taka, że ${\displaystyle r^{2}\equiv 2\!\!\!\!{\pmod {q}}.}$ Zatem na mocy Małego Twierdzenia Fermata: ${\displaystyle 2^{p}-1=r^{q-1}-1\equiv 0\!\!\!\!{\pmod {q}}.}$

Przykłady: ${\displaystyle p=11,\ 23,\ 83.}$

Przypisy

Linki zewnętrzne

• The Great Internet Mersenne Prime Search (GIMPS) (ang.)
• Eric W.E.W. Weisstein Eric W.E.W., Mersenne Prime, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).
• Eric W.E.W. Weisstein Eric W.E.W., Perfect Number, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).
• Liczby pierwsze Mersenne’a (ang.)