Liczby pierwsze Mersenne'a

Co się właśnie stało?

Liczby Mersenne'a to liczby postaci $M_p = 2^p - 1$. Dla niektórych wykładników $p$ liczba ta jest pierwsza — nazywamy ją wtedy liczbą pierwszą Mersenne'a:

Przykłady: $2^2-1=3$, $2^3-1=7$, $2^5-1=31$, $2^7-1=127$ — wszystkie pierwsze. Ale $2^{11}-1 = 2047 = 23\cdot 89$ jest już złożona, mimo że 11 jest liczbą pierwszą.

Kluczowa własność (niezmiennik):

Aby $2^p-1$ mogło być liczbą pierwszą, sam wykładnik $p$ musi być liczbą pierwszą:

Implikacja działa tylko w jedną stronę. Gdyby $p = a\cdot b$ było złożone, to $2^a-1$ dzieliłoby $2^p-1$ — więc liczba nie byłaby pierwsza. Odwrotnie jednak być nie musi: nie każde pierwsze $p$ daje pierwszą liczbę Mersenne'a (kontrprzykład: $p=11$).

Skąd nazwa i dlaczego to ważne?

Liczby te noszą imię francuskiego mnicha i uczonego Marina Mersenne'a, który w 1644 r. („Cogitata Physico-Mathematica") podał listę wykładników $p$dających — jak sądził — liczby pierwsze. Jego lista zawierała kilka błędów, poprawionych dopiero w XX w. Liczby pierwsze Mersenne'a są ściśle związane z liczbami doskonałymi (wzór Euklidesa–Eulera).

Dlaczego rekordy należą do Mersenne'a?

Dla liczb tej postaci istnieje wyjątkowo szybki test pierwszości — test Lucasa–Lehmera — działający wyłącznie dla $2^p-1$. Dlatego rekordowo wielkie znane liczby pierwsze to niemal zawsze liczby Mersenne'a. Projekt GIMPS (Great Internet Mersenne Prime Search, od 1996 r.) wykorzystuje moc obliczeniową tysięcy komputerów-ochotników z całego świata; największa znana liczba pierwsza (2024 r.) ma ponad 41 milionów cyfr.

Po co Ci to na maturze:

To modelowy przykład, że warunek konieczny nie musi być wystarczający: „$p$ pierwsze" jest konieczne, by $2^p-1$ było pierwsze, ale nie gwarantuje pierwszości. Umiejętność odróżnienia implikacji od równoważności to klasyczny temat egzaminacyjny — a liczby pierwsze są fundamentem współczesnej kryptografii.

Zapamiętaj: $M_p = 2^p-1$; jeśli $2^p-1$ jest pierwsza, to $p$też — ale nie na odwrót. Największe znane liczby pierwsze to liczby Mersenne'a, znajdowane dziś przez projekt GIMPS.