Pewne liczby naturalne wyróżnia się ze względu na ich interesujące własności lub znaczenie praktyczne. Szczególnie ważny zbior stanowią liczby pierwsze. Są to liczby naturalne większe od jeden, podzielne tylko przez jeden i przez samą siebie. Jedyną liczbą pierwszą parzystą jest dwójka, a wszystkie pozostałe są nieparzyste. Liczb pierwszych mniejszych od 100 jest 25. Oto one:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Każda liczba naturalna większa od jedynki daje się przedstawić w jeden i tylko jeden sposób jako iloczyn liczb pierwszych i jest to jedno z podstawowych twierdzeń teorii liczb. Liczby pierwsze są w tym sensie jakby cegiełkami, z których złożone są wszystkie inne liczby. Czynniki pierwsze to liczby pierwsze występujące w przedstawieniu danej liczby naturalnej w postaci iloczynu (tzw. rozkład na czynniki pierwsze). Jeżeli znamy rozkład liczby, możemy prawie od razu podać wszystkie dzielniki danej liczby oraz liczbę tych dzielników. Daną liczbę nazywamy złożoną jeśli jest iloczynem co najmniej dwóch liczb pierwszych. Zatem każda liczba naturalna większa od jedynki jest pierwsza albo złożona.

np:. 868 = 2 * 2 * 7 * 31

Euklides już około roku 300 p.n.e udowodnił, że istnieje nieskończenie wiele liczb pierwszych. Dowód Euklidesa jest dowodem nie wprost. Przypuśćmy, że istnieje skończona ilość n liczb pierwszych. Oznaczmy przez p_k k-tą z kolei liczbę pierwszą. p_n jest więc ostatnią liczbą pierwszą. Utwórzmy liczbę K = p₁p₂…p_n + 1. Jest ona złożona, więc zawsze ma co najmniej jeden dzielnik pierwszy r > 1. Oczywiście liczba pierwsza r nie może być żadną z liczb p₁, p₂, …, p_n, bo w przeciwnym razie r byłaby dzielnikiem różnicy K-p₁p₂…p_r = 1, co jest niemożliwe. Istnieje zatem jeszcze jedna liczba pierwsza r, więc liczby p₁, p₂, …, p_n nie mogą być wszystkimi liczbami pierwszymi. Zawsze istnieje liczba pierwsza inna, niż te, które już znamy. Wobec tego jest ich nieskończenie wiele.

Jest wiele problemów związanych z liczbami pierwszymi, które do dziś nie są rozstrzygnięte. Nie znamy ich dokładnego rozmieszczenia w zbiorze liczb naturalnych ani dobrej metody na poszukiwanie wielkich liczb pierwszych. Znając pewną liczbę pierwszą na ogół nie wiemy jaka będzie następna. Metoda sita Eratostenesa (Eratostenes z Cyreny ok. 276-196 p.n.e.) pozwala dość szybko znajdować liczby pierwsze, ale nie nadaje się (w swojej pierwotnej postaci) do poszukiwania wielkich liczb.

Metoda ta polega na wypisaniu w kolejności wszystkich liczb nie większych od danej liczby naturalnej n. Z tego zbioru wykreśla się wszystkie liczby parzyste większe od 2, potem podzielne przez 3 większe od 3 i kolejno wykreślamy wielokrotności najmniejszej dotychczas nie skreślanej liczby (bez niej samej). Po zakończeniu tej procedury pozostaną nie skreślone wszystkie liczby pierwsze mniejsze od n, bo są one tylko swoją własną wielokrotnością. Zauważmy, że nie musimy sprawdzać wszystkich liczb, bo wiemy, że po przekroczeniu nie skreślimy już żadnej.

Załóżmy, że napiszemy pewną dużą liczbę n i chcemy stwierdzić, czy jest ona liczbą pierwszą. Możemy oczywiście spróbować ją podzielić przez każdą znaną liczbę pierwszą nie większą niż pierwiastek z n. Jeśli to się nie uda (tzn. ani razu nie podzieli się bez reszty) to będziemy mogli z pewnością stwierdzić, że n jest pierwsza. Dla dużych liczb zajmowałoby to bardzo dużo czasu, dlatego już w XVII wieku Pierre de Fermat szukał innego kryterium, które pozwoliłoby stwierdzić, czy dana liczba jest pierwsza, czy złożona. Jednym ze znalezionych przez niego kryteriów jest tzw. Małe Twierdzenie Fermata.

Fermat szukał także wyrażenia F(n), które dla każdej wartości n dawałoby tylko liczby pierwsze. Przypuszczał, że takim wyrażeniem będzie F(n) = . Rzeczywiście:

F(0) = 3, F(1) = 5, F(2) = 17, F(3) = 257, F(4)= 65537

są liczbami pierwszymi, ale Euler wykazał, że F(5) = 4294967297 nie jest liczbą pierwszą, bo dzieli się przez 641 i przez 6700417. Liczby pierwsze postaci nazywamy obecnie liczbami pierwszymi Fermata. Nie wiadomo jednak, czy istnieje skończona ilość liczb pierwszych Fermata, czy jest ich nieskończenie wiele. Dotychczas znanych jest 5 liczb Fermata pierwszych i ponad 80 złożonych.

Liczby pierwsze pojawiają się często przy stosowaniu kombinatoryki w geometrii. Gauss udowodnił, że do tego, aby można było zbudować za pomocą cyrkla i linijki n-kąt foremny, potrzeba i wystarcza, żeby n było iloczynem potęgi liczby 2 (o wykładniku > 0) i różnych liczb pierwszych będących właśnie liczbami Fermata.

Wzoru na liczby pierwsze po Fermacie poszukiwali także Christian Goldbach i Leonhard Euler. Goldbach podczas poszukiwań sformuował pewną hipotezę znaną dziś jako Hipoteza Goldbacha. Mówi ona, że każda liczba parzysta większa od dwóch jest sumą dwóch liczb pierwszych. Hipoteza Goldbacha jest wyjątkowo prosto sformuowana, ale mimo to do dziś nie jest znany jej dowód. Na tego, kto ją udowodni czekała nawet nagroda wysokości miliona dolarów (już nieaktualne). Euler znalazł w 1772 roku pewien ciekawy wzór znany dziś jako ciąg Eulera. Jest to ciąg o wyrazie ogólnym

Charakteryzuje się tym, że aż 40 jego początkowych wyrazów to liczby pierwsze, dopiero wyraz a₄₁ jest liczbą złożoną. Goldbach i Euler udowodnili jednak wspólnie że nie istnieje wielomian całkowity W(x) o współczynnikach całkowitych, którego wartości dla całkowitych x byłyby tylko liczbami pierwszymi. Gdyby zatem istniał wzór na kolejne liczby pierwsze, nie byłby to na pewno wielomian. Wiemy, że każde wyrażenie analityczne można przybliżyć z dowolną dokładnością przez pewien wielomian (tzw. rozwinięcie Taylora). Dlatego właśnie uważa się powszechnie, że nie istnieje wzór na liczby pierwsze. Ostatnio jednak pewne znaczące rezultaty dają próby zapisania algorytmu sita Eratostenesa przy pomocy ciągów rekurencyjnych. Czyżby liczbami pierwszymi rządził jakiś fraktal? Kwestia wzoru na kolejne liczby pierwsze (lub wzoru generującego wyłącznie liczby pierwsze niekoniecznie kolejne) jest wciąż otwarta. Entuzjaści prześcigają się w znajdowaniu coraz ciekawszych wzorów. Na przykład w roku 1993 A. Moran, P. Pritchard i A.Thyssen znaleźli 22 liczby pierwsze spełniające zależność liniową

F(n) = 11410337850553 + 4609098694200*n, gdzie n = 0, 1, …, 21.

Wiele różnych problemów teorii liczb pozwala roztrzygnąć słynne twierdzenie Dirichleta, które głosi że jeżeli liczby naturalne a i r >= 2 są względnie pierwsze (tzn. nie mają wspólnych dzielników oprócz jedynki) to ciąg arytmetyczny a, a+r, a+2r, … zawiera nieskończenie wiele liczb pierwszych. Dowód tego twierdzenia jest jednak trudny i nieelementarny.

Ważnym wzorem z pogranicza teorii liczb i analizy matematycznej jest tzw. tożsamość Eulera: , gdzie w iloczynie po lewej p przyjmuje wszystkie wartości liczb pierwszych zaczynając od 2, a w sumie po prawej k przebiega cały ciąg liczb naturalnych. Tożsamość tą można udowodnić i to właśnie ona zapoczątkowała falę niesamowitych zastosowań analizy w teorii liczb, które zaowocowały wieloma istotnymi wynikami. Z faktu, że szereg po prawej stronie wzoru jest rozbieżny dla n = 1 wynika też, że istnieje nieskończenie wiele liczb pierwszych.

Wiemy, że dla dowolnej liczby naturalnej m istnieje taka liczba pierwsza p, że najbliższa liczba pierwsza jest odległa od p o co najmniej 2m+2. Oznacza to, że istnieją dowolnie daleko odległe od siebie kolejne liczby pierwsze (różnica kolejnych może być dowolnie duża).

Czebyszew udowodnił, że dla każdej liczby naturalnej n > 1 istnieje co najmniej jedna taka liczba pierwsza p, że n < p < 2n. Jeżeli zatem p_k oznacza k-tą liczbę pierwszą, to spełniona jest nierówność p_k+1 < 2p_k. Inaczej p_k+1 – p_k < p_k, czyli kolejna liczba pierwsza po p jest zawsze oddalona od p o mniej niż p. Twierdzenie to w połączeniu z tym, że istnieją dowolnie odległe kolejne liczby pierwsze pozwala również wnioskować, że liczb pierwszych jest nieskończenie wiele.

Kres dolny zbioru liczb postaci sqrt(p_k+1)-sqrt(p_k), czyli zbioru różnic pierwiastków kolejnych liczb pierwszych wynosi zero. Kolejna hipoteza głosi, że ta różnica jest zawsze mniejsza od 1. Gdyby tak było, to pomiędzy dwoma dowolnymi kolejnymi kwadratami liczb naturalnych znajdowałaby się na pewno co najmniej jedna liczba pierwsza. Tego jednak nie dowiedziono.

Liczby bliźniacze to dwie kolejne liczby pierwsze różniące się dokładnie o 2, np. 5 i 7, 11 i 13, 17 i 19, 101 i 103. Największą znaną obecnie (rok 1999) parą liczb bliźniaczych jest para 318032361*2107001 ± 1 znaleziona przez Underbakke’a i Carmody’ego. Nie wiadomo dotychczas, czy takich par jest nieskończenie wiele. Rozmieszczenie liczb pierwszych w ciągu liczb naturalnych jest bardzo nieregularne, a teoria liczb pierwszych stanowi obecnie jeden z najważniejszych działów teorii liczb, ściśle powiązany z analizą matematyczną. Problem z odkryciem prawa rozmieszczenia liczb pierwszych polega głównie na tym, że takie liczby bliźniacze występują nawet bardzo daleko od zera. Poza tym zawsze można znaleźć taką liczbę pierwszą, że następna w kolejności będzie dowolnie daleko od niej.

Wprowadza się nawet specjalną funkcję π(x) oznaczającą ilość liczb pierwszych mniejszych lub równych x. Znane jest tzw. asymptotyczne prawo rozkładu liczb pierwszych: . Niewiele ono jednak mówi o dokładnym rozkładzie liczb pierwszych, choć samo w sobie jest i tak wielkim osiągnięciem analitycznym. Podana tu postać tego prawa jest jedną z prostszych. Znane są bowiem o wiele od niej dokładniejsze wyrażone przez więcej nieelementarnych całek.

Liczby Mersenne’a – nazwane tak od nazwiska uczonego francuskiego M. Mersenne’a (1588-1648), który je badał – to liczby postaci 2ⁿ – 1, gdzie n jest naturalne. Jak dotąd nie wiadomo, czy wśród liczb Mersenne’a jest nieskończenie wiele liczb pierwszych, chociaż największe znane obecnie liczby pierwsze są właśnie liczbami Mersenne’a. Największą (rok 2008) znalezioną liczbą pierwszą Mersenne’a i 46 z kolei jest 2^42643801-1, liczba ta zapisana w systemie dziesiętnym składa się z ponad 12 milionów cyfr.

Poszukiwaniem coraz większej liczby pierwszej zajmuje się kilkadziesiąt tysięcy ochotników z całego świata. Używają do tego swoich domowych komputerów. Za pomocą Internetu łączą się z serwerem GIMPS, który koordynuje ich działania: rozdziela zadania, zbiera wyniki i kontroluje przebieg poszukiwań.

Liczby zaprzyjaźnione to takie liczby m i n spełniające następujący warunek: suma wszystkich dzielników naturalnych liczby m (mniejszych od m) jest równa n i jednocześnie suma wszystkich dzielników naturalnych liczby n (mniejszych od n) jest równa m. Najmniejsze różne liczby zaprzyjaźnione to 220 i 284. Inną parę takich liczb tworzą 1184 i 1210. Okazuje się, że liczby mogą być zaprzyjaźnione same ze sobą. Są to tzw. liczby doskonałe, czyli liczby równe sumie wszystkich swoich dzielników mniejszych od nich samych. Są dość niesamowite. Pierwsze cztery z nich, to:

6 = 1 + 2 + 3,
28 = 1 + 2 + 4 + 7 + 14,
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248,
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064

Można udowodnić następujące twierdzenie (patrz W. Sierpiński „Teoria liczb”): Każdą parzystą liczbę doskonałą można przedstawić w postaci: 2^p-1(2^p – 1), gdzie 2^p – 1 jest liczbą pierwszą. Zwróćmy uwagę, że dla p = 2 otrzymujemy 6, a dla p = 3 otrzymujemy 28. Do roku 1994 znaleziono tą metodą tylko 35 liczb doskonałych. Największą znaną liczbę doskonałą otrzymuje się dla p = 216 091. Jak dotąd nie wiemy jeszcze, czy istnieją nieparzyste liczby doskonałe. Wydaje się to nieprawdopodobne, ale…

Liczby pierwsze dzięki swoim wyjątkowym własnościom znajdują zastosowanie w kryptografii. W roku 1978 Rivest, Shamir i Adleman opracowali algorytm szyfrujący oparty na tym, że nie znamy żadnego efektywnego sposobu rozkładania w krótkim czasie iloczynów dużych liczb pierwszych na czynniki. Dzisiaj szyfr nazywany RSA (od nazwisk jego twórców) uważany jest za najbezpieczniejszy system klucza publicznego. Załóżmy, że osoba A chce wysłać poufną wiadomość do osoby B. Aby skorzystać z szyfru RSA należy wybrać dwie duże liczby pierwsze p i q i pomnożyć je n = pq. Oblicza się następnie wartość tzw. funkcji Eulera φ(n) dla liczby n: φ(n) = (p-1)(q-1), po czym wybiera jakąkolwiek liczbę e względnie pierwszą z φ(n). O tym, czy dwie liczby są względnie pierwsze (tzn. nie mają wspólnych dzielników większych od 1), można się przekonać znajdując ich NWD, czyli największy wspólny dzielnik (np. za pomocą algorytmu Euklidesa lub algorytmu kolejnych dzieleń). Liczba e stanowi wraz z liczbą n klucz do szyfrowania. Kluczem do odszyfrowywania będzie taka liczba d, dla której iloczyn ed przy dzieleniu przez φ(n) daje resztę 1. Liczbę d wyznacza się również poszukując NWD. Liczby p i q utrzymuje się koniecznie w tajemnicy, przy czym nie musi ich znać żadna z osób A i B. Jeżeli wiadomość (tekst jawny) potraktujemy jak dużą liczbę całkowitą x, to funkcja szyfrująca jest teraz określona wzorem y = f(x) = x^e mod n, a funkcja deszyfrująca wzorem x = g(y) = y^d mod n. Funkcja g jest zatem funkcją odwrotną do funkcji f. Nie jest dotychczas znany żaden algorytm pozwalający obliczyć liczbę d, gdy znane są liczby n i e. Jedyna właściwie metoda polega na rozłożeniu liczby n na czynniki i powtórzeniu powyżej opisanego postępowania. Osoba A może ogłosić liczby n i e razem jako tzw. klucz publiczny. Osoba B chcąc wysłać zaszyfrowaną wiadomość do osoby A, oblicza wartość funkcji f dla wiadomości x i wynik wysyła do osoby A. Założenie jest takie, że tylko osoba A zna liczby d i n (klucz prywatny) i tylko ona potrafi obliczyć wartość funkcji g i odszyfrować wiadomość. Zaszyfrowana wiadomość może być więc odczytana jedynie przez osobę posiadającą klucz prywatny. Szyfr RSA jest wprawdzie bardzo bezpieczny, ale za to stosunkowo wolny zatem jego zakres stosowalności jest dość ograniczony i zwykle stosuje się go w połączeniu z innymi szybszymi metodami szyfrowania aby tylko zwiększyć ich bezpieczeństwo.

Do skonstruowania szyfru RSA potrzebne są duże liczby pierwsze. Zbadanie, czy dana liczba całkowita jest liczbą pierwszą, okazuje się znacznie mniej czasochłonne niż rozłożenie liczby złożonej tej samej wielkości na jej czynniki pierwsze. Tylko z pozoru oba te problemy wyglądają na identyczne. Aby się przekonać, że liczba jest złożona, trzeba znaleźć jeden z jej dzielników, ale aby się przekonać, że liczba jest pierwsza, trzeba pokazać, że takiego dzielnika nie ma, co jest znacznie bardziej pracochłonne. To powszechne przekonanie jest jednak błędne! Można bowiem skonstruować testy wykorzystujące zaawansowane metody teorii liczb, które pozwalają stwierdzić, czy dana liczba jest pierwsza w inny sposób niż poprzez poszukiwanie jej ewentualnych dzielników!

Najprostszy taki test polega na zastosowaniu Małego Twierdzenia Fermata, mówiącego, że jeśli liczba p jest pierwsza i liczba a nie dzieli się przez p, to liczba a^p-1 przy dzieleniu przez p daje resztę 1, czyli a^p-1 mod p = 1. Jeśli np. weźmiemy liczbę p = 481 i liczbę a = 2, to drogą nietrudnych obliczeń możemy przekonać się, że 2⁴⁸⁰ mod 481 = 248. Wyciągamy stąd wniosek, że liczba 481 nie jest liczbą pierwszą, choć ta metoda nie pozwala na znalezienie dzielnika liczby 481. Oczywiście w przypadku tak małych liczb możemy również łatwo znaleźć rozkład liczby p na czynniki pierwsze: 481 = 13 * 37, ale w przypadku dużych liczb sposób ten może być znacznie bardziej skuteczny. Okazuje się jednak, że ten test nie pozwala z całą pewnością stwierdzić, że liczba jest złożona, np. liczba p = 561 ma tę własność, że jeśli liczba a jest względnie pierwsza z 561, to a⁵⁶⁰ mod 561 = 1, mimo iż liczba 561 jest złożona. Udowodniono, że takich liczb (zwanych liczbami Carmichaela) jest nieskończenie wiele. Zastosowanie jeszcze jednego twierdzenia o liczbach pierwszych: jeśli liczba p jest pierwsza i a² mod p = 1, to albo a mod p = 1, albo a mod p = p – 1, łącznie z małym twierdzeniem Fermata, pozwala mimo to skonstruować bardzo skuteczny test, łatwy do zaprogramowania nawet na słabszych komputerach. Popatrzmy na jeszcze jeden przykład. Gdybyśmy testując liczbę 481 wybrali niefortunnie podstawę a = 11, to by się okazało, że 11⁴⁸⁰ mod 481 = 1. Zauważamy jednak, że 11⁴⁸⁰ = (11²⁴⁰)². Możemy więc spróbować obliczyć 11²⁴⁰ mod 481. Wynik nadal będzie równy 1, ale liczba 11²⁴⁰ jest też kwadratem liczby 11¹²⁰ itd. Okaże się, że 11⁴⁸⁰ mod 481 = 11²⁴⁰ mod 481 = 11¹²⁰ mod 481 = 11⁶⁰ mod 481 = 1, lecz 11³⁰ mod 481 = 38. Oczywiście liczba 38 jest różna zarówno od 1, jak i od 480, czyli nawet ta wydawałoby się niefortunnie dobrana liczba a = 11 też okazała się skuteczna. Można dowieść, że jeśli liczba p jest złożona, to co najmniej 75% liczb a mniejszych od p pozwoli wykazać za pomocą tego poprawionego testu, że rzeczywiście jest ona złożona. Ten nowy test (od nazwisk twórców nazywany Testem Millera-Rabina) polega na wielokrotnym losowaniu różnych liczb a. Jeśli za którymś razem okaże się, że liczba p jest złożona, to mamy pewność, że jest tak w istocie. Jeśli natomiast za każdym razem otrzymamy wynik 1 lub p-1, to nadal nie wiemy, czy liczba p jest pierwsza czy złożona. Gdyby jednak liczba p była liczbą pierwszą, wielokrotnie musielibyśmy losować niefortunnie jedną z tych 25% liczb złych. Jeśli wykonamy 100 takich losowań, prawdopodobieństwo, że wszystkie losowania będą niefortunne, jest niezwykle małe (wynosi 1/2²⁰⁰), czyli w praktyce możemy przyjąć, że liczba p jest pierwsza. Mamy więc do czynienia z tzw. testem probabilistycznym, który jest przy tym bardzo szybkim testem. Udowodniono również, że przy założeniu nie udowodnionej dotychczas uogólnionej hipotezy Riemanna można łatwo przekształcić ten test w tzw. test deterministyczny, dający zawsze odpowiedź pewną. Znane są inne testy probabilistyczne i deterministyczne, działają one jednak znacznie wolniej i są znacznie bardziej skomplikowane.

Algorytm RSA pozostaje niezłamany ponieważ nie można szybko rozłożyć dużych liczb na (również duże) czynniki pierwsze. Krąży opinia, że zadanie to jest wykonalne tylko dla komputerów dysponujących wystarczająco dużą mocą obliczeniową. Opracowano jednak teoretycznie pewną metodę (tzw. Algorytm Shora) pozwalającą błyskawicznie znajdować dzielniki dużych liczb. Algorytm ten nie jest jednak możliwy do wykonania na jakimkolwiek z istniejących dzisiaj komputerów. Potrzebuje on komputera kwantowego, którego zasada działania jest zupełnie inna niż dzisiejszych komputerów. Przy jego pomocy wykonuje się obliczenia przypisując każdemu możliwemu wynikowi pewne prawdopodobieństwo, a następnie pozwalając tym prawdopodobieństwom „wpływać na siebie” tak, żeby te, które nie prowadzą do właściwego wyniku zmalały, a te właściwe – wzrosły.

Liczby pierwsze fascynowały matematyków od dawna, między innymi dlatego, że pytania zadawane w związku z liczbami pierwszymi są wyjątkowo proste, a jednocześnie tak podstawowe, że wciąż ogarnia nas zdumienie, kiedy zdajemy sobie sprawę z tego, że nie znamy na te pytania odpowiedzi. Prawie każdy matematyk zajmujący się liczbami pierwszymi doświadcza wrażenia, że obcuje z jakąś odwieczną, niezbadaną, ale idealną tajemnicą. Podobne uczucie od wieków każe ludziom badać wszystko to, co dotychczas niezbadane. Jednak współczesne metody są tak bardzo zaawansowane, że można prawie z pewnością twierdzić, że kolejne szokujące odkrycia w tej dziedzinie nastąpią już niedługo. A najlepsze jest to, że każdy z nas może się do tego przyczynić.