Rekordowe pierwszaki

Liczby pierwsze (czyli takie, które mają dokładnie dwa dzielniki naturalne) interesowały matematyków od zarania dziejów. Już Euklides w IV w. p.n.e. dowiódł, że jest ich nieskończenie wiele. Dowód przeprowadzony przez Euklidesa jest przykładem tzw. rozumowania „nie wprost". Zakłada się, że liczb pierwszych jest skończenie wiele, i bada, jakie byłyby tego konsekwencje. Oczywiście natychmiast otrzymuje się sprzeczność, bo jeśli {p₁, p₂, p₃, ..., p_n} byłby zbiorem wszystkich liczb pierwszych, to liczba P = p₁p₂p₃ ·...· p_n+1 do tego zbioru nienależąca (bo jest przecież większa od wszystkich jego elementów) również byłaby pierwsza, gdyż nie dzieli się przez żadną liczbę pierwszą (w każdym takim dzieleniu daje resztę 1).

W III w. p.n.e. Eratostenes z Cyreny podał pewien sposób znajdowania liczb pierwszych w skończonych początkowych podzbiorach liczb naturalnych - tzw. sito Eratostenesa. Jest to metoda kolejnego „wysiewania" liczb pierwszych spośród liczb naturalnych większych od 1. Wybieramy najmniejszą liczbę (2) i kolorujemy ją, a potem wykreślamy wszystkie jej wielokrotności (czyli skreślamy mechanicznie co drugą liczbę). Z pozostałych liczb (niepokolorowanych i nieskreślonych) wybieramy pierwszą wolną liczbę (3), kolorujemy, a potem wykreślamy wszystkie jej wielokrotności (niektóre liczby będą w tym procesie skreślane wiele razy). Powtarzamy to postępowanie, aż wszystkie liczby będą skreślone lub pokolorowane. Te kolorowe to będą właśnie liczby pierwsze. 

Od XVII wieku nowych liczb pierwszych szuka się głównie wśród tzw. liczb Mersenne'a, czyli liczb postaci 2^p -1, gdzie p jest pierwsze, choć nie wiadomo, czy jest wśród nich nieskończenie wiele liczb pierwszych ani czy jest wśród nich nieskończenie wiele liczb złożonych. Oczywiście gdy p jest złożone, 2^p-1 pierwsze być nie może, wszak liczba 2^nm-1 dzieli się przez 2ⁿ-1 (dlaczego?). Sam Marin Mersenne [czyt. mar'ę mer'sen] (1588-1648) - francuski mnich franciszkański i matematyk - przypuszczał, że wśród liczb postaci 2^p-1 znajdują się prawie wszystkie liczby pierwsze (tzn. wszystkie poza ew. pewną skończoną liczbą). Matematycy współcześni nadal się nad tym głowią. Mersenne twierdził też (bez dowodu), że liczby 2^p-1 są pierwsze dla p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 i dla żadnych innych liczb naturalnych p<258. Po 300 latach okazało się, że popełnił pięć błędów. Liczby pierwsze otrzymamy także dla p = 61, 89 i 107, a dla p = 67 i 257 otrzymamy liczby złożone. Tym błędom nie należy się dziwić zważywszy na to, że liczby Mersenne’a rosną bardzo szybko, a w tamtych czasach wszystkie obliczenia wykonywano ręcznie. Już wskazanie dzielników liczby 2047 = 2¹¹ – 1 jest dość trudne, a co dopiero liczby 536870911 = 2²⁹ – 1.

Każda liczba złożona musi mieć dzielnik nieprzekraczający pierwiastka kwadratowego z tej liczby (dlaczego?). W oparciu o tę własność można zbadać, czy dana liczba p jest pierwsza - wystarczy sprawdzić, czy nie dzieli się przez żadną z liczb pierwszych mniejszych lub równych √p. Jednak jeśli p jest dużą liczbą, sprawdzenie tego faktu jest bardzo żmudne. Tylko dzięki niezwykłej zręczności rachunkowej matematyk szwajcarski Leonard Euler [czyt. ojler] (1707-1783) udowodnił około 1772 roku, że liczba 2³¹-1 = 2 147 483 647 jest pierwsza. Znajdowanie większych liczb pierwszych bez dodatkowych "sztuczek rachunkowych" byłoby trudne.

Jedną z takich "sztuczek" odkrył francuski matematyk Adrien-Marie Legendre [czyt. adri’ę mar’i le’żądr] (1752-1833). Pokazał, że dzielnikami liczby Mersenne’a z wykładnikiem p mogą być tylko liczby postaci 2kp+1 (kN), dające z dzielenia przez 8 resztę 1 lub 7. Na przykład dzielnikami 2¹¹-1 są liczby 23 = 2·11+1 = 7 (mod 8) oraz 89 = 2·4·11+1 = 1 (mod 8). Ograniczyło to znacznie liczbę możliwych dzielników, jakie należy sprawdzać przy badaniu pierwszości liczby Mersenne’a. Ale i tak dla dużych liczb rachunki te pozostały upiorne. A jak Wam poszło szukanie dzielników liczby 2²⁹-1? (O pewnej ciekawostce związanej z osobą Adriena Legendre'a piszemy na Portalu tutaj.)

Przed erą komputerów przez prawie 80 lat największą znaną liczbą pierwszą była odkryta przez kolejnego matematyka francuskiego Françoisa Edouarda Lucasa [nazwisko czytaj frąsu'a edu'ar liu'ka] (1842-1891) w 1876 roku liczba 2¹²⁷-1 = 170 141 183 460 469 231 731 687 303 715 884 105 727 (ma ona 39 cyfr). Jej pierwszości nie dałoby się udowodnić ani sitem Erastotenesa, ani metodą sprawdzania podzielności, ale Lucas odkrył kolejną "sztuczkę". Podany przez niego warunek stwierdzał, że liczba 2^p-1, gdzie p jest pierwsza, sama jest liczbą pierwszą wtedy i tylko wtedy, gdy jest dzielnikiem wyrazu L_p-1 ciągu określonego następująco: L₁=4, L_n=L_n-1² - 2. Nie wiadomo, jak Lucas wymyślił tę własność. Wiemy, że nie potrafił jej formalnie udowodnić.

Warunek podany przez Lucasa został udowodniony dopiero dopiero w XX wieku przez Amerykanina Derricka Henry'ego Lehmera (1905-1991). Ta metoda stosowana jest w dowodzeniu pierwszości liczb Mersenne'a do dziś (choć od tamtej pory wynaleziono jeszcze inne "sztuczki") i nosi nazwę testu Lucasa-Lehmera.  Kolejne wyrazy ciągu L_n to 4, 14, 194, 37634… (nie należy mylić ich z tzw. liczbami Lucasa, powstającymi analogicznie do liczb Fibonacciego, ale z początkowych wyrazów równych 1 i 2). Można sprawdzić, że 2³-1|L₃, 2⁵-1|L₄, ale jak sprawdzić bez kalkulatora, że 2¹²⁷-1|L₁₂₈? A jednak Lucas tego dokonał. Czy potrafisz zrobić to na komputerze?

Jak widać bez komputerów skuteczne poszukiwanie nowych liczb pierwszych byłoby niemożliwe. Następną po liczbie znalezionej przez Lucasa liczbę pierwszą Mersenne'a odkrył Raphael Mitchel Robinson (1911-1995) z Uniwersytetu Kalifornijskiego z Los Angeles dopiero w 1952 roku, używając do tego Standards Western Automatic Computer - prymitywnego komputera lampowego. Liczba odkryta przez Robinsona to 2⁵²¹-1. Ma ona 157 cyfr. Współczesne komputery pierwszość tej liczby sprawdzają w kilkanaście sekund przy użyciu prostych algorytmów. 

Rozwój techniki sprawia, że liczba znanych liczb pierwszych szybko rośnie. Na początku XX wieku znane były wszystkie liczby pierwsze poniżej miliona, a na początku XXI wieku - wszystkie poniżej 2 miliardów. Jest ich ponad 98 milionów, chociaż w ogóle znanych jest dużo więcej liczb pierwszych (np. te znalezione przez Lucasa i Robinsona) tylko niekolejnych. Jednak nadal nie znamy efektywnego wzoru na wyznaczenie nieskończenie wielu takich liczb (o wzorze opisującym wszystkie liczby pierwsze, choć nie nadającym się do ich obliczania możesz przeczytać w artykule Czy istnieje wzór na n-tą liczbę pierwszą?).

Poszukiwanie dużych liczb pierwszych jest dziś bardzo ważnym problemem. Mają one zastosowanie we współczesnej kryptografii, czyli teorii kodowania informacji. Jest to także znakomita reklama dla firm komputerowych i programistów, gdyż do zbadania pierwszości liczby nie wystarczy zapuścić jakiegoś prostego algorytmu i wystarczająco długo czekać. Komputery wykonują przecież działania na liczbach o ograniczonej liczbie cyfr, a współcześnie w grę wchodzą liczby o milionach cyfr. W 2006 r. wykazano pierwszość liczby 2^{32 582 657}-1 . Jej zapis dziesiętny ma 9 808 358 cyfr. Była to 44. poznana liczba pierwsza Mersenne'a (ale nie wiadomo, czy znane są już wszystkie liczby Mersenne'a od niej mniejsze). 

Dlatego od wielu lat prowadzi się zbiorowe poszukiwania nowych liczb pierwszych. Może do nich dołączyć każdy, np. w ramach międzynarodowego programu GIMPS (Great Internet Mersenne Prime Search). Wystarczy przeczytać więcej o tym projekcie na stronie http://www.mersenne.org i pobrać z niej odpowiednie oprogramowanie, które działa automatycznie w wolnym czasie komputera. Taka działalność przy odrobinie szczęścia może okazać się niezwykle dochodowa.

Aby zachęcić społeczeństwo do udziału we wspólnych poszukiwaniach Electronic Frontier Foundation ogłosiła ufundowanie nagrody w wysokości 50 000 dolarów za odkrycie pierwszej liczby pierwszej o więcej niż milionie cyfr (wypłacono ją w 2000 roku) oraz 100 000 dolarów dla odkrywcy pierwszej w historii liczby pierwszej o więcej niż 10 milionach cyfr. Ta pula została rozbita 23 sierpnia 2008 r. Tego dnia na Uniwersytecie Kalifornijskim w Los Angeles (tam gdzie pracował niegdyś Robinson) komputer pracujący w sieci GIMPS PrimeNet odkrył 45. pierwszą liczbę Mersenne'a, która wynosi 2^{43 112 609}-1  i ma 12 978 189 cyfr. Gratulacje należą się Edsonowi Smithowi - człowiekowi odpowiedzialnemu za zainstalowanie (jako screen savera) i utrzymanie oprogramowania GIMPS na Wydziale Matematyki UCLA. Zaledwie 2 tygodnie później 6 września 2008 roku niemiecki inżynier, pasjonat projektu GIMPS - Hans Michael Elvenich z Langenfeld koło Kolonii odkrył 46. znaną pierwszą liczbę Mersenne'a wynoszącą 2^{37 156 667}-1 (ma 11 185 272 cyfr, więc jest mniejsza niż amerykańska rekordzistka, ale również spełnia warunki nagrody). Był to pierwszy przypadek od 1988 roku gdy liczby Mersenne'a nie były odkryte w kolejności rosnącej wielkości.

W kwietniu 2009 znaleziono (a w czerwcu 2009 zweryfikowano) 47. liczbę pierwszą Mersenne'a!
Jest nią 2^42643801-1. Liczba ta ma 12 837 064 cyfr i została znaleziona przez Odda Magnara Strindmo z Melhus w Norwegii (w ramach projektu GIMPS). Jest to druga co do wielkości znana w tej chwili liczba pierwsza (jest większa niż 46. i mniejsza niż 45. liczba Mersenne'a) i jest 13. znalezioną w ramach projektu GIMPS w jego 13-letniej historii.  

Zgodnie z obietnicą administratorzy projektu GIMPS wypłacą 50 000 dolarów Wydziałowi Matematyki na Uniwersytecie Kalifornijskim, 25 000 podzielą między odkrywców poprzednich 6 liczb Mersenne'a, a 25 000 przekażą na cele charytatywne. Następne nagrody wyznaczone przez EFF wynoszą: 150 000 dolarów za przekroczenie 100 mln cyfr oraz 250 000 dolarów za przekroczenie miliarda cyfr. Więcej o tej fundacji można przeczytać na stronie http://www.eff.org.

Na koniec pytanie dla Czytelników: ile trwałoby zapisanie aktualnie rekordowej liczby pierwszej na papierze i ile papieru byłoby na to potrzebne?