Historia liczb naturalnych sięga tak daleko wstecz, że trudno jednoznacznie określić nie tylko to kiedy, ale także gdzie pojawiły się one po raz pierwszy. Przypuszcza się więc, że proste operacje liczbowe towarzyszyły ludziom od zawsze. Na przykład prehistoryczni myśliwi znali i rozróżniali pojęcia takie jak nic, jeden, dwa oraz wiele, które wykorzystywali do opisywania liczby upolowanych zwierząt. A skoro już o zwierzętach mowa — dowiedziono naukowo, że różne gatunki zwierząt z łatwością rozpoznają liczności niewielkich zbiorów. Liczenie nie jest więc wyłącznie ludzką zdolnością, ale tylko w przypadku ludzi rozwinęło się tak bardzo. Jak to się stało?

Rozwój człowieka wiązał się naturalnie ze wzrostem umiejętności liczenia. Było tak choćby dlatego, że rozrost plemion oraz rozwój technik łowieckich, hodowlanych i handlowych wymuszał precyzyjne operowanie na coraz to większych wartościach. Duże liczby naturalne były też przydatne do określania wielkości wrogich plemion i wielkości zasobów, które można było od tych plemion zagrabić.

Zdobyte mniej lub bardziej moralnie trofea stanowiły nierzadko dobro wspólne. Samodzielne łowy odeszły w niepamięć, a grupy myśliwych i grabieżców współpracowały z sobą w celu zapewnienia wyżywienia i dobrostanu swoim rodzinom. Naturalne stało się więc pytanie, w jaki sposób pewne zasoby (np. 12 zagrabionych ubrań lub 7 upolowanych saren) można uczciwie podzielić. Szybko okazało się, że niektóre zbiory można podzielić na kilka równych części tylko tak, że każda część będzie zawierała dokładnie jeden element. Dowody historyczne wskazują na to, że niewielkie liczby opisujące rozmiary takich zbiorów (zwane dziś liczbami pierwszymi) były znane ludziom zamieszkującym tereny obecnego Kongo już 20 tysięcy lat temu.

Dziś liczby naturalne i własności ich dzielników wykorzystuje się tak powszechnie, że większość z nas nie zdaje sobie z tego sprawy. Na przykład, projektanci układów napędowych, w których stosuje się łańcuchy napędzające koła zębate dbają o to, aby liczba ogniw łańcucha i liczba zębów koła zębatego były wartościami względnie pierwszymi (a więc takimi, których jedynym wspólnym dzielnikiem jest 1). Dzięki temu łańcuch zużywa się równomiernie. Innym przykładem mogą być powszechnie stosowane algorytmy szyfrowania z kluczem publicznym, których implementacje opierają się na losowym generowaniu bardzo dużych liczb pierwszych.

Myli się jednak ten, kto sądzi, że o liczbach naturalnych wiemy już wszystko. Jednym z ważnych problemów współczesnej matematyki obliczeniowej jest (a właściwie był) problem znalezienia algorytmu, który dla dowolnej liczby naturalnej potrafiłby szybko określić, czy jest ona pierwsza. Pierwszy taki algorytm udało się znaleźć dopiero w 2002 roku — do tego czasu nie było nawet wiadomo, czy jest to możliwe. Dziś matematycy zastanawiają się, czy istnieje algorytm, który dla dowolnej liczby naturalnej potrafi szybko znaleźć wszystkie jej dzielniki. i chociaż oba te problemy stanowią jedynie niewielki promil tego, czym zajmuje się obecna teoria liczb, to jednak będą bardzo ważne w czasie naszej fascynującej podróży, która — mam nadzieję — raz na zawsze zmieni Twoje myślenie o liczbach.

Liczby pierwsze

Liczby naturalne to dodatnie liczby całkowite: 1, 2, 3, 4, itd. Jak zapewne doskonale pamiętasz z zajęć matematyki w szkole, liczb naturalnych jest nieskończenie wiele. Każda z nich ma także dzielniki, które same są liczbami naturalnymi. Na przykład liczba $6$ dzieli się przez $1$, $2$, $3$ i $6$, liczba $14$ dzieli się przez $1$, $2$, $7$ i $14$, a liczba $5$ dzieli się przez $1$ i $5$. Jeśli liczba naturalna ma dokładnie dwa różne dzielniki, to mówimy, że jest liczbą pierwszą. Oto kilka początkowych liczb o takiej własności: $$2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$$

Liczbę naturalną, która ma więcej niż dwa dzielniki możemy zapisać jako iloczyn kilku liczb naturalnych większych od $1$ — taką liczbę nazywamy więc złożoną. Na przykład liczba $28$ jest liczbą złożoną, ponieważ $28 = 2 \cdot 14$. Liczba $1$ ma tylko jeden dzielnik — nie jest więc ani liczbą pierwszą, ani liczbą złożoną.

Już od czasów starożytnych wiedziano, że niektóre liczby złożone można przedstawić w postaci iloczynu mniejszych liczb na kilka różnych sposobów (np. $28 = 2 \cdot 14$, a równocześnie $28 = 4 \cdot 7$). Szybko okazało się jednak, że istnieje dokładnie jeden sposób, w jaki można przedstawić dowolną liczbę złożoną jako iloczyn liczb pierwszych (np. $28 = 2 \cdot 2 \cdot 7$). Pierwszy znany dowód tego faktu pojawił się już w IV w. p.n.e. w zbiorczej publikacji Euklidesa, zatytułowanej Elementy. Jego zwartą wersję, nazywaną przed matematyków podstawowym twierdzeniem arytmetyki, można sformułować następująco.

Twierdzenie (Podstawowe twierdzenie arytmetyki). Każda liczba naturalna większa od $1$ jest albo liczbą pierwszą, albo da się ją jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.

W Elementach Euklidesa można znaleźć dowody wielu innych interesujących twierdzeń dotyczących liczb pierwszych. Jeden z nich zasługuje jednak na szczególną uwagę, ponieważ jest uznawany za wiodący przykład dowodu przez sprowadzenie do sprzeczności. Jest przy tym intuicyjny i krótki — spełnia więc wszystkie warunki, abyśmy mogli go tu przedstawić.

Twierdzenie. Istnieje nieskończenie wiele liczb pierwszych.

Stwierdzenie, że zbiór liczb pierwszych jest nieskończony, nie jest wcale takie oczywiste, jak mogłoby się wydawać na pierwszy rzut oka. w czasach Euklidesa pojęcie nieskończoności nie było jeszcze do końca ugruntowane, a filozofowie zgadzali się jedynie co do istnienia nieskończoności potencjalnej — zgodnej z naszą intuicją nieskończoności zbioru liczb naturalnych. Mówiąc precyzyjniej, zbiór jest nieskończony potencjalnie, jeśli zawiera więcej niż $k$ elementów, niezależnie od tego, jakie $k$ wybierzemy. Dokładnie ten sposób rozumowania wykorzystany jest w dowodznie powyższego twierdzenia.

Załóżmy na chwilę, że zbiór liczb pierwszych jest skończony i zawiera dokładnie $q$ elementów, które oznaczymy symbolami $p_1, p_2, \dots, p_q$. Rozważmy teraz liczbę $$\mathcal{P} = p_1 \cdot p_2 \cdot \dots \cdot p_q + 1.$$
Istnieją tylko dwie możliwości: liczba $\mathcal{P}$ jest albo liczbą pierwszą, albo liczbą złożoną (dlaczego nie może być równa 1?). Jeśli $\mathcal{P}$ jest liczbą złożoną, to dzieli się przez którąś z liczb pierwszych. Zauważmy jednak, że w wyniku dzielenia $\mathcal{P}$ przez $p_1$ otrzymujemy resztę $1$, a więc $\mathcal{P}$ nie dzieli się przez $p_1$. Stosując analogiczne rozumowanie dla pozostałych liczb na liście możemy łatwo pokazać, że $\mathcal{P}$ nie dzieli się przez żadną z wartości $p_1, p_2, \dots, p_q$ — a przecież założyliśmy, że to wszystkie liczby pierwsze. Oznacza to nic innego niż to, że $\mathcal{P}$ jest liczbą pierwszą różną od każdej z liczb $p_1, p_2, \dots, p_q$, co stoi w sprzeczności z założeniem, że lista $p_1, p_2, \dots, p_q$ jest pełna. Zbiór liczb pierwszych ma więc więcej niż $q$ elementów, a to oznacza, że jest nieskończony.

W poszukiwaniu liczb pierwszych

Liczby pierwsze wykorzystuje się w matematyce dość powszechnie, szczególnie w dziedzinach związanych z teorią liczb, algebrą, algorytmiką i przetwarzaniem informacji. Niektórych matematyków od samych liczb pierwszych bardziej interesują jednak sposoby ich odnajdywania.

Jednym z najstarszych algorytmów wykorzystywanych do przeczesywania ciągu liczb naturalnych w poszukiwaniu liczb pierwszych jest algorytm znany pod nazwą sita Erastotenesa. Najstarsza znana historykom wzmianka o tej metodzie pojawia się w dziele Nikomachosa z Gerazy, zatytułowanym Wprowadzenie do arytmetyki i datowanym na 60–120 r. n.e. To właśnie tam Nikomachos opisuje wspomniany algorytm i przypisuje jego autorstwo Erastotenesowi z Cyreny, greckiemu matematykowi żyjącemu w latach 276–194 p.n.e.

Sito Erastotenesa pozwala szybko wyznaczyć wszystkie liczby pierwsze mniejsze od zadanej wartości granicznej. Idea algorytmu leży w tym, aby z listy potencjalnych liczb pierwszych systematycznie wykreślać te wartości, które na pewno pierwsze nie są. Aby zaprezentować tę metodę, posłużymy się prostym przykładem. Załóżmy, że chcemy wyznaczyć liczby pierwsze mniejsze lub równe $50$. Pierwszy krok polega na utworzeniu listy wszystkich liczb naturalnych od $2$ do $50$ włącznie i zapisaniu takiej listy, na przykład w formie tabeli.

$$\begin{matrix}
& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\
21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\
31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40\\
41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50\\
\end{matrix}$$

Na elementach tej listy wykonujemy cyklicznie dwie operacje: odnajdywania kolejnej liczby pierwszej i wykreślania wszystkich jej wielokrotności. Rozpoczynamy od liczby $2$ — najmniejszej nieskreślonej dotąd liczby. Oznaczamy ją w jakiś sposób (na przykład kolorem czerwonym) i wykreślamy z listy (oznaczamy kolorem jasnoszarym) wszystkie jej wielokrotności: $4, 6, 8, \dots, 50$. Te liczby z pewnością nie są pierwsze, bo każda z nich dzieli się przez $2$.

$$\begin{matrix}
& \color{red}{2} & 3 & \color{lightgray}{4} & 5 & \color{lightgray}{6} & 7 & \color{lightgray}{8} & 9 & \color{lightgray}{10}\\
11 & \color{lightgray}{12} & 13 & \color{lightgray}{14} & 15 & \color{lightgray}{16} & 17 & \color{lightgray}{18} & 19 & \color{lightgray}{20}\\
21 & \color{lightgray}{22} & 23 & \color{lightgray}{24} & 25 & \color{lightgray}{26} & 27 & \color{lightgray}{28} & 29 & \color{lightgray}{30}\\
31 & \color{lightgray}{32} & 33 & \color{lightgray}{34} & 35 & \color{lightgray}{36} & 37 & \color{lightgray}{38} & 39 & \color{lightgray}{40}\\
41 & \color{lightgray}{42} & 43 & \color{lightgray}{44} & 45 & \color{lightgray}{46} & 47 & \color{lightgray}{48} & 49 & \color{lightgray}{50}\\
\end{matrix}$$

Z pozostałych liczb wybieramy najmniejszą — tutaj $3$. Jest to kolejna liczba pierwsza. Oznaczamy ją więc i wykreślamy z listy wszystkie jej złożone wielokrotności: $6, 9, 12, \dots, 48$.

$$\begin{matrix}
& \color{red}{2} & \color{red}{3} & \color{lightgray}{4} & 5 & \color{lightgray}{6} & 7 & \color{lightgray}{8} & \color{lightgray}{9} & \color{lightgray}{10}\\
11 & \color{lightgray}{12} & 13 & \color{lightgray}{14} & \color{lightgray}{15} & \color{lightgray}{16} & 17 & \color{lightgray}{18} & 19 & \color{lightgray}{20}\\
\color{lightgray}{21} & \color{lightgray}{22} & 23 & \color{lightgray}{24} & 25 & \color{lightgray}{26} & \color{lightgray}{27} & \color{lightgray}{28} & 29 & \color{lightgray}{30}\\
31 & \color{lightgray}{32} & \color{lightgray}{33} & \color{lightgray}{34} & 35 & \color{lightgray}{36} & 37 & \color{lightgray}{38} & \color{lightgray}{39} & \color{lightgray}{40}\\
41 & \color{lightgray}{42} & 43 & \color{lightgray}{44} & \color{lightgray}{45} & \color{lightgray}{46} & 47 & \color{lightgray}{48} & 49 & \color{lightgray}{50}\\
\end{matrix}$$

Lista potencjalnych liczb pierwszych kurczy się błyskawicznie. Najmniejszą nieskreśloną dotąd liczbą jest liczba $5$. Wiadomo już, co z tym faktem zrobić. Podobnie ustalamy, że kolejną — po piątce — liczbą pierwszą jest liczba $7$. Oba kroki zaprezentowane zostały na poniższych szkicach.

$$\begin{matrix}
& \color{red}{2} & \color{red}{3} & \color{lightgray}{4} & \color{red}{5} & \color{lightgray}{6} & 7 & \color{lightgray}{8} & \color{lightgray}{9} & \color{lightgray}{10}\\
11 & \color{lightgray}{12} & 13 & \color{lightgray}{14} & \color{lightgray}{15} & \color{lightgray}{16} & 17 & \color{lightgray}{18} & 19 & \color{lightgray}{20}\\
\color{lightgray}{21} & \color{lightgray}{22} & 23 & \color{lightgray}{24} & \color{lightgray}{25} & \color{lightgray}{26} & \color{lightgray}{27} & \color{lightgray}{28} & 29 & \color{lightgray}{30}\\
31 & \color{lightgray}{32} & \color{lightgray}{33} & \color{lightgray}{34} & \color{lightgray}{35} & \color{lightgray}{36} & 37 & \color{lightgray}{38} & \color{lightgray}{39} & \color{lightgray}{40}\\
41 & \color{lightgray}{42} & 43 & \color{lightgray}{44} & \color{lightgray}{45} & \color{lightgray}{46} & 47 & \color{lightgray}{48} & 49 & \color{lightgray}{50}\\
\end{matrix}$$

$$\begin{matrix}
& \color{red}{2} & \color{red}{3} & \color{lightgray}{4} & \color{red}{5} & \color{lightgray}{6} & \color{red}{7} & \color{lightgray}{8} & \color{lightgray}{9} & \color{lightgray}{10}\\
11 & \color{lightgray}{12} & 13 & \color{lightgray}{14} & \color{lightgray}{15} & \color{lightgray}{16} & 17 & \color{lightgray}{18} & 19 & \color{lightgray}{20}\\
\color{lightgray}{21} & \color{lightgray}{22} & 23 & \color{lightgray}{24} & \color{lightgray}{25} & \color{lightgray}{26} & \color{lightgray}{27} & \color{lightgray}{28} & 29 & \color{lightgray}{30}\\
31 & \color{lightgray}{32} & \color{lightgray}{33} & \color{lightgray}{34} & \color{lightgray}{35} & \color{lightgray}{36} & 37 & \color{lightgray}{38} & \color{lightgray}{39} & \color{lightgray}{40}\\
41 & \color{lightgray}{42} & 43 & \color{lightgray}{44} & \color{lightgray}{45} & \color{lightgray}{46} & 47 & \color{lightgray}{48} & \color{lightgray}{49} & \color{lightgray}{50}\\
\end{matrix}$$

Z ostatniej tabeli możemy natychmiast odczytać, że kolejną liczbą pierwszą jest $11$. w tym miejscu możemy jednak zakończyć algorytm, ponieważ najmniejszą liczbą złożoną, której każdy czynnik jest większy lub równy $11$ jest $11 \cdot 11 = 121$, a więc liczba znacząco wykraczająca poza rozważany przedział. Oznacza to też, że wszystkie nieskreślone dotąd liczby są liczbami pierwszymi:

$$\begin{matrix}
2 & 3 & 5 & 7 & 11 & 13 & 17 & 23 & 29 & 31\\
37 & 41 & 43 & 47 & 49 \\
\end{matrix}$$

Sito Erastotenesa jest najszybszym znanym algorytmem poszukiwania wszystkich liczb pierwszych mniejszych lub równych zadanej wartości. Niestety, algorytm ten nie nadaje się zbytnio do poszukiwania dużych liczb pierwszych. Powód jest jeden — przyrostowe budowanie ciągu liczb pierwszych okazuje się przekleństwem, gdy interesuje nas tylko największa z nich.

Na przykład, gdybyśmy chcieli — stosując sito Erastotenesa — znaleźć największą liczbę pierwszą mniejszą od miliarda, musielibyśmy wykonać około dziesięciu miliardów (a dokładnie $\sum_{k=2}^{\lfloor\sqrt{10^9}\rfloor} \lfloor 10^9/k \rfloor = 9\,938\,824\,259$) operacji skreślenia elementu z listy. To niewiele, jeśli chcemy poznać wszystkie liczby pierwsze występujące po drodze (przy okazji, jest ich $50\,847\,534$), ale bardzo dużo, gdy interesuje nas tylko największa z nich (czyli $999\,999\,937$).

Wielu matematyków poświęca się poszukiwaniom wzorca, który porządkowałby zbiór liczb pierwszych. Wszystko jednak wskazuje na to, że rozkład liczb pierwszych w zbiorze liczb naturalnych jest w miarę równomierny, ale nieprzewidywalny. Jeśli weźmiemy pod uwagę twierdzenie Euklidesa (przypomnijmy: liczb pierwszych jest nieskończenie wiele), to nie powinno nas dziwić to, że matematycy szybko zaczęli się przechwalać kto ma większą. Aktualny tytuł mistrzowski należy do Jonathana Pace’a — 26 grudnia 2017 roku opublikował on numeryczny dowód pierwszości liczby, której zapis dziesiętny wymaga aż $23\,249\,425$ cyfr. Jak to możliwe?

Liczby Mersenne’a

Liczbą Mersenne’a nazywamy każdą liczbę postaci $M_k = 2^k – 1$, gdzie $k$ jest liczbą naturalną. Wartości tej postaci otrzymały swoje imię na cześć żyjącego na przełomie XVI i XVII w. francuskiego matematyka, Marina Mersenne’a. To on skonstruował pierwszą tablicę liczb tego typu i rozpoczął tym samym wieloletni proces ich analizowania. Jeśli zastanowisz się przez chwilę, na pewno zauważysz, że $$M_k = 2^k – 1 = 2^0 + 2^1 + \dots + 2^{k-1}.$$ Każda wartość $M_k$ jest więc sumą pewnego skończonego ciągu geometrycznego. Z liczbami Mersenne’a związane jest pewne ciekawe twierdzenie, które stało się furtką do poszukiwania olbrzmich liczb pierwszych.

Twierdzenie. Jeśli liczba $M_k$ jest pierwsza, to liczba $k$ jest pierwsza.

Skoro tak, to szukając liczb pierwszych postaci $M_k = 2^k – 1$ wystarczy ograniczyć się do tych wartości $k$, które same są liczbami pierwszymi. Dlaczego jednak powyższe twierdzenie jest prawdziwe? Przyjmijmy, że $k$ jest liczbą złożoną, a więc da się zapisać w postaci iloczynu dwóch mniejszych liczb naturalnych różnych od $1$, np. $k = a \cdot b$. Wtedy
\[\begin{array}{rl}
M_k & = 2^{a \cdot b} – 1 =\\
& = (2^a)^b – 1^b =\\
& = (2^a – 1)\cdot(2^{a\cdot(b-1)} + 2^{a\cdot(b-2)} + \dots + 2^{a\cdot(b-b)}), \\
\end{array}\]
co oznacza, że $M_k = 2^k – 1$ dzieli się przez $M_a = 2^a – 1$. Skoro tak, to $M_k$ jest liczbą złożoną, bo założyliśmy przecież, że $a \neq 1$. (Co by było, gdybyśmy tego nie założyli?) Do dzisiaj nie wiadomo jednak, czy jest nieskończenie wiele liczb pierwszych Mersenne’a. Nie przeszkadza to jednak w odnajdywaniu kolejnych wartości tego typu.

Wspomniany już wcześniej Jonathan Pace bierze udział w projekcie GIMPS, w ramach którego bada się pierwszość liczb Mersenne’a. To właśnie w ramach tego projektu — wykorzystując przez sześć dni bez przerwy moc obliczeniową zwykłego komputera domowego będącego własnością Jona — pokazano, że liczba $2^{77232917} -1$ jest liczbą pierwszą. To wystarczyło Pace’owi do zdobycia sławy, przynajmniej na chwilę.

Tytuł największej liczby pierwszej w rękach (cyfrach?) liczby Mersenne’a to nie niespodzianka — aż $9$ z $10$ największych znanych obecnie liczb pierwszych jest liczbami Mersenne’a i nic nie wskazuje na to, aby statystyka ta miała się w najbliższym czasie pogorszyć.

Co dalej?

Poszukiwanie coraz to większych liczb pierwszych jest wspaniałą rozrywką, ale uzyskiwane w ten sposób wartości już dawno wykroczyły poza praktyczne potrzeby. w stosowanych na co dzień algorytmach wykorzystuje się obecnie liczby pierwsze, które można zapisać z wykorzystaniem około 150 cyfr dziesiętnych. Choć zabrzmi to niewiarygodnie, takie liczby można uzyskać najszybciej drogą… losowania. Jak? To fascynujący temat na kolejny artykuł.

---

Artykuł został przygotowany przy wsparciu pozyskanemu przez Poznańską Fundację Matematyczną od Miasta Poznań na realizację projektu ,,Potęga matematyki''.