W niniejszej podrozdziale podamy podstawowe informacje i własności dotyczące liczb pierwszych. Liczby pierwsze można widzieć jako podstawowe składniki, z których zbudowane są liczby cakowite.
Definicja 2.3.1 ( liczba pierwsza). Liczbę całkowitą \(p\in \Z \) nazywamy liczbą pierwszą, jeśli spełnione są następujące warunki:
(1) \(p>1\);
(2) \(\forall d\in \N :\;d|p\;\Longrightarrow \; d=1\;\mbox {lub}\; d=p\).
Zbiór wszystkich liczb pierwszych oznaczamy dalej przez \(\mathcal {P}\).
Każdą liczbę naturalną większą od jedynki, nie będącą liczbą pierwszą nazywamy liczbą złożoną.
Pamiętajmy dalej o umowie, iż liczba jeden nie jest ani liczbą pierwszą ani też liczbą złożoną.
Definicja liczby pierwszej i proste zastosowanie identyczności Bezouta prowadzi nas do następującego wniosku.
Warto zaznaczyć, że własność 2.3.2 charakteryzuje liczby pierwsze. Dokładniej, stosując tę własność można wprowadzić definicję liczby pierwszej. Jest to o tyle ciekawe z naszego punktu widzenia, że w przyszłości własność „braku istotnego rozkładu” elementu (jak to jest w przypadku liczby pierwszej, gdzie rozkłada się ona wyłącznie na iloczyn \(p\cdot 1\), względnie \((-p)\cdot (-1)\)) oraz 2.4.2(2) okażą się być nierównoważne w ogólniejszych strukturach. Te problemy doprowadzą nas do definicji odpowiednio elementów nierozkładalnych i elementów pierwszych, (por. III).
Własność 2.3.2(2) w wersji dla \(n=2\) to nic innego jak wspomniany wcześniej Lemat Euklidesa, który pojawia się w VII Księdze Elementów, sformułowany dla przypadku dwóch liczb. Gauss 4 w swoim dziele Disquisitiones arithmeticae wypowiada lemat Euklidesa i dowodzi przy jego pomocy twierdzenie o rozkładzie liczb całkowitych na liczby pierwsze, z którego to twierdzenia bezpośrednio wynika też gaussowskie uogólnienie lematu Euklidesa. Jak się często podkreśla „lemat Gaussa” pojawia się już jednak wcześniej w pracy Nouveaux éléments de mathématiques Jeana Presteta 5 z XVII wieku.
Definicja, którą teraz wprowadzimy może razić przerostem formy nad treścią. Znów wytłumaczeniem niech będą nasze przyszłe zamierzenia, gdzie słowo „ jedność” oznaczać będzie znacznie szerszą klasę elementów niż jest to w przypadku zbioru \(\Z \).
Definicja 2.3.4 ( rozkład jednoznaczny). Niech \(k\in \Z ^\star \). Mówimy, że \(k\) posiada jednoznaczny rozkład na iloczyn liczb pierwszych, jeśli
(1) istnieją \(p_1,\dots ,p_r\in \mathcal {P}\), \(u\in U(\Z )\) takie, że \(k=u\cdot p_1\cdot \ldots \cdot p_r\);
(2) dla dowolnych dwóch układów \(p_1,\dots ,p_r\in \mathcal {P}\), \(q_1,\dots ,q_s\in \mathcal {P}\), \(u,v\in U(\Z )\) takich, że
\[k=u\cdot p_1\cdot \ldots \cdot p_r=v\cdot q_1\cdot \ldots \cdot q_s\]
mamy \(r=s\) oraz istnieje taka funkcja \(\sigma \) - bijekcja zbioru \(\{1,\ldots , r\}\) na siebie, że: \(\forall \ i\in \{1,\dots ,r\}: \ p_i=q_{\sigma (i)}\).
Dowód. Wystarczy oczywiście wykazać twierdzenie dla liczb naturalnych większych od jedynki. W naturalny sposób dowód rozbija się na dwie części: wykazanie istnienia rozkładu i wykazanie jego jednoznaczności.
Istnienie. Indukcja względem \(n\): dla \(n=2\) teza jest spełniona.
Załóżmy, że teza jest spełniona dla takich liczb naturalnych \(m\), że \(1<m<n\). Jeśli \(n\) jest liczbą pierwszą, to dowód jest zakończony. Jeśli \(n\) nie jest liczbą pierwszą, to \(n=ab\), gdzie \(1<a<n\) i \(1<b<n\). Wobec tego, z założenia indukcyjnego liczby \(a\) i \(b\) są liczbami pierwszymi bądź iloczynami liczb pierwszych. W konsekwencji \(n\) również jest iloczynem liczb pierwszych.
Jednoznaczność. Ponownie indukcja względem \(n\).
Dla \(n=2\) jednoznaczność rozkładu jest oczywista ze względu na pierwszość tej liczby. Gdyby bowiem było \(n=p_1\cdot \ldots \cdot p_r\) gdzie \(p_i\in \mathcal {P}\) i \(r>1\), to \(2\) musiałaby dzielić jedną z liczb \(p_i\) a tym samym być jej równa (wobec pierwszości). Wtedy dzieląc obie strony przez \(2\) mielibyśmy, że pozostałe liczby pierwsze \(p_j\) dzielą jedynkę co jest niemożliwe. Wobec tego \(r=1\) i \(p_1=2\).
Zakładając tezę dla liczb mniejszych lub równych \((n-1)\), gdzie \(n>2\) przypuśćmy, że dla \(n\), mamy dwa rozkłady:
\[ n=p_1\cdot \ldots \cdot p_r=q_1\cdot \ldots \cdot q_s, \]
gdzie \(p_i, q_j\in \mathcal {P}\) oraz \(p_1\leqslant \ldots \leqslant p_r\), \(q_1\leqslant \ldots \leqslant q_s.\) Oczywiście możemy przyjąć, że \(r>1\). Istotnie, w przeciwnym razie mamy do czynienia z liczbą pierwszą
i teza zachodzi. Niech zatem \(p\) będzie najmniejszą liczbą pierwszą dzielącą \(n\). Oznacza to, że \(p\) dzieli \(p_i\) dla pewnego \(i\),
(2.3.2(2)). W konsekwencji \(p=p_i\) i z minimalności \(p\) otrzymujemy równość \(p=p_1\). Rozumując analogicznie dostajemy \(p=q_1\).
Niech teraz \(m:=\f {n}{p}<n\). Wobec tego mamy rozkład:
\[ m=p_2\cdot \ldots \cdot p_r=q_2\cdot \ldots \cdot q_s. \]
Z założenia indukcyjnego otrzymujemy \(r=s\) i istnieje taka bijekcja \(\widetilde \sigma \) zbioru \(\{2,\ldots , n\}\) na siebie, (permutacja tego zbioru), że \(\forall \ i\in \{2,\dots ,r\}\) \(p_i=q_{\widetilde \sigma (i)}\). Przyjmując \(\sigma (1)=1\), \(\sigma (i)=\widetilde \sigma (i)\), dla \(i>1\) otrzymujemy poszukiwaną permutację zbioru \(\{1,\ldots , n\}\).
□
Dowód. Dla dowodu niewprost przypuśmy, że \(\mathcal {P}=\{p_1,\dots , p_r\}\) i zdefinujmy liczbę \(M:=p_1\cdot \ldots \cdot p_r+1\). Jest jasne, że żadna z liczby \(p_{1},\ldots , p_{r}\) nie dzieli \(M\). W przeciwnym razie liczba 1 byłaby podzielna przez liczbę pierwszą. Niech zatem \(p\) będzie liczbą pierwszą dzielącą \(M\), (taka istnieje na mocy 2.3.5). Wobec tego \(p\notin \mathcal {P}\) i \(p\) jest liczbą pierwszą, co prowadzi do sprzeczności. □
Skoro już wiemy, że liczb pierwszych jest nieskończenie wiele powstaje naturalne pytanie: jak wiele jest liczb pierwszych \(\leq x\), gdzie \(x\) jest ustaloną liczbą rzeczywistą? Innymi słowy interesuje nas szybkość wzrostu funkcji
\[ \pi (x)=|\{p:\;p\leq x\;\mbox {oraz}\;p\in \mathcal {P}\}|. \]
Funkcja \(\pi (x)\) nazywana jest funkcją zliczającą liczby pierwsze. Gauss przypuszczał, zaś J. Hadamard 6 i Ch. J. de la Vallée-Poussin 7 udowodnili niezależnie tzw. Twierdzenie o liczbach pierwszych, tj. równość
\[ \lim _{x\rightarrow +\infty }\frac {\pi (x)\log x}{x}=1. \]
Dowód tego twierdzenia wymaga zastosowaniu zaawansowanego aparatu funkcji analitycznych. Można jednak podać zupełnie elementarny dowód dolnego oszacowania na funkcję \(\pi (x)\), które wymaga tylko podstawowych własności liczb całkowitych. Dokładniej pokażemy dowód Erdősa8 następującego twierdzenia.
Dowód. Zanim rozpoczniemy dowód przypomnijmy, że liczba naturalna nazywana jest bezkwadratową, jeśli nie jest podzielna przez kwadrat żadnej liczby pierwszej. Oznaczmy zbiór liczb bezkwadratowych przez \(B\).
Dla \(n\in \N \) rozważmy zbiór
\[ A(n)=\{(a,b)\in \N \times B:\;a^2b\leq n\} \]
i zauważmy, że \(|A(n)|=n\). Istotnie, każdą liczbą naturalną \(m\) można jednoznacznie zapisać w postaci \(m=a^2b\), gdzie \(a\in \N \) i \(b\in B\).
Jeśli \((a,b)\in A(n)\), to mamy oczywiście \(a^2\leq n\) i \(b\leq n\), i w konsekwencji \(a\leq \sqrt {n}\). Ponadto liczba \(b\) jest bezkwadratowa, więc jest iloczynem różnych liczb pierwszych, z których każda jest \(\leq n\). Oznacza to, że \(b\) daje sie zapisać jako iloczyn liczb liczb ze zbioru \(\{p_{1},p_{2},\ldots ,p_{\pi (n)}\}\). Możliwych iloczynów mamy \(2^{\pi (n)}\). Podsumowując nasze rozważania widzimy, że jeśli \((a,b)\in A(n)\), to mamy co najwyżej \(\sqrt {n}\) możliwych wyborów liczby \(a\) oraz \(2^{\pi (n)}\) możliwych postaci liczby \(b\). Stąd \(|A(n)|<\sqrt {n}2^{\pi (n)}\), ale \(|A(n)|=n\), więc ostatecznie \(n\leq \sqrt {n}2^{\pi (n)}\) i w konsekwencji
\[ \pi (n)\geq \frac {\log n}{2\log 2}. \]
□
W tej chwili istnieje całe multum dowodów nieskończoności zbioru wszystkich liczb pierwszych. Zaprezentowany powyżej dowód, w dość podobnej wersji jak w Elementach jest uznawany za pierwszy zapisany dowód przeprowadzony
metodą niewprost i choćby z tego powodu jest tym dowodem, z którym warto się zapoznać.
Liczby pierwsze obecnie to punkt wyjścia do analizy całego bogactwa problemów nie tylko stricte teorioliczbowych, o których nie sposób opowiedzieć w kilku słowach. Wspomnieć jednak wypada o wciąż udoskonalanych testach pierwszości,
których celem jest zbadanie pierwszości zadanej liczby, (nie zaś jej rozkład na liczby pierwsze co jest zagadnieniem znacznie trudniejszym). Już w okolicach 200 p.n.e. grecki matematyk Eratosthenes 9wprowadził metodę wyznaczania liczb pierwszych nie większych od ustalonej liczby \(n\) zwaną odtąd ”sitem Eratosthenesa”. Jej działanie jest niezwykle proste - wypisujemy wszystkie liczby od
2 do \(n\) następnie zakreślamy 2 jako liczbę pierwszą i wykreślamy jej wszystkie wielokrotności. Potem zakreślamy pierwszą pozostałą liczbę i wykreślamy wszystkie jej wielokrotności i tak kontynuujemy aż nie ma ”nietkniętych” liczb
mniejszych lub równych od \(\sqrt n\). W ten sposób otrzymamy tablicę liczb pierwszych nie większych od liczby wyjściowej.
Obecne, o wiele bardziej zaawansowane metody testowania pierwszości dzielą się na dwa rodzaje: testy deterministyczne i probablistyczne. Do tych pierwszych zaliczyć można m.in. test Lucasa-Lehmera, 10 (przy użyciu tego testu znaleziono największe liczby pierwsze, test dotyczy badania pierwszości tzw. liczb Mersenne’a) 11,
czy niektóre testy oparte na krzywych eliptycznych. Testy probablistyczne, choć nie pozwalają na zdecydowanie z pewnością, czy dana liczba jest pierwsza mają tę przewagę, że zwykle są dużo szybsze od testów
deterministycznych. Liczby, którym udaje się przejść pozytywnie test probablistyczny, ale mimo to okazują się być jednak liczbami złożonymi znane są w kontekście liczb "pseudopierwszych". Istnieje wiele różnych rodzajów takich
liczb, z których bodaj najbardziej znane to liczby pseudopierwsze Fermata, które mimo iż pozostają liczbami złożonymi to spełniają założenia Małego Twierdzenia Fermata, o którym opowiemy dalej. Przy okazji testów
probablistycznych wypada wspomnieć o dwóch testach: teście Rabina-Millera, który jest wyjątkowo efektywnym testem probablistycznym oraz o tzw. teście AKS (od nazwisk twórców: Manindra Agrawala, Neeraja Kayala i Nitina Saxena, 2002),
który to test deterministyczny sprawdza pierwszość zadanej liczby w czasie wielomianowym, słowem jego czas działania jest ograniczony za pomocą zależności wielomianowej od rozmiaru danych wejściowych. Do czasu pojawienia się tego
testu zasadniczo nie było dowodu na to, iż test pierwszości zadanej liczby jest problemem rozwiązywalnym w czasie wielomianowym mimo, iż uważano że taka możliwość istnieje.
4 Carl Friedrich Gauss: matematyk, fizyk i astronom niemiecki, (1777-1855), nazywany „księciem matematyków”
5 Jean Prestet: matematyk francuski, (1648-1690)
6 Jacques Hadamard: matematyk francuski (1865–1963)
7 Charles Jean de la Vallée-Poussin: matematyk francuski (1866–1962)
8 Paul Erdős: matematyk węgierski, jednen z najwybitniejszych matematyków XX w. Autor ponad 1500 artykułów dotyczących głównie teorii liczb, kombinatoryki i teorii grafów (1913-1996)
9 Eratosthenes: grecki matematyk, poeta, geograf, astronom i filozof (276-194 p.n.e.)