Teoria liczb jest dziedziną matematyki, zajmującą się badaniem własności liczb – początkowo tylko naturalnych. Obecnie należałoby powiedzieć: głównie naturalnych. Jej początki sięgają starożytności. Zajmowali się nią Pitagoras, Euklides, Eratostenes, Diofantos i wielu innych. Bujny rozwój teorii liczb datuje się mniej więcej od czasów działalności Pierre'a Fermata (1601-1665), autora wypowiedzi słynnego Wielkiego Twierdzenia Fermata. Do dwudziestego wieku powszechną była opinia, iż teoria ta nie ma żadnego zastosowania. Jednak dzięki wielkiemu rozwojowi kryptografii - nauki zajmującej się układaniem i łamaniem szyfrów - pogląd ten musiał zostać zweryfikowany.
W dwu kolejnych wykładach poznamy podstawowe pojęcia i klasyczne twierdzenia teorii liczb - niektóre pochodzące jeszcze z czasów starożytnych. Zainteresowanych zachęcamy do rozszerzenia swej wiedzy w kursie Matematyka Dyskretna 2, gdzie przedstawiony jest system kryptograficzny RSA, oparty na tych podstawowych faktach z teorii liczb.
Uwaga
W wykładach poświęconych teorii liczb wszystkie liczby są całkowite, chyba że wyraźnie jest powiedziane inaczej.
Uwaga
W wykładach dotyczących teorii liczb poznamy też kilka algorytmów operujących na liczbach naturalnych. Rozważając ich złożoność musimy poczynić kilka założeń o złożoności podstawowych operacji arytmetycznych. Długość liczby \( n \) to liczba bitów \( n \), czyli liczba cyfr w zapisie binarnym (dwójkowym). Wynosi ona \( \lfloor \lg{n}\rfloor+1 \), ale nam wystarcza wiedzieć, że jest ona \( O(\lg{n}) \). Przyjmujemy, że złożoność dodawania liczb \( a \) i \( b \) jest proporcjonalna do sumy ich długości, dokładniej że jest \( O(\lg{a}+\lg{b}) \) oraz że złożoność mnożenia liczb \( a \) i \( b \) jest \( O(\lg{a}\lg{b}) \) (choć znane są szybsze algorytmy).
Dowolną liczbę wymierną \( a \) można wydzielić przez dowolną niezerową liczbę wymierną \( b \) i wynik tego działania jest liczbą wymierną. Ograniczając sie jednak zbioru \( \mathbb{Z} \) liczb całkowitych, nie każde dzielenie jest wykonalne: \( 15:3=5 \), \( -22:2=-11 \) ale \( 31:3= \)?. Rozważamy więc dzielenie liczb całkowitych z resztą.
Niech \( b>0 \), wtedy dla każdej liczby całkowitej \( a \) istnieją jednoznacznie wyznaczone: iloraz \( q \) i reszta \( r \) spełniające:
\( a=bq+r\qquad\textrm{i}\qquad 0\leq r < b. \)
Resztę \( r \) z dzielenia \( a \) przez \( b \) zapisujemy też jako: \( a \ {\sf mod}\ b \).
Przykład
\( 47 \ {\sf mod}\ 9 =2 \), \( 1823 \ {\sf mod}\ 2 =1 \), \( 32 \ {\sf mod}\ 43 =32 \), \( 111 \ {\sf mod}\ 13 =7 \), \( -3 \ {\sf mod}\ 7 =4 \). W pewnych sytuacjach reszta równa jest \( 0 \), np. \( -22=-2\cdot 11+0 \).
\( b \) dzieli \( a \) (lub \( a \) jest podzielne przez \( b \), co zapisujemy \( b|a \), jeśli istnieje \( q \) takie, że \( b=aq \). W takim wypadku mówimy też, że \( b \) jest dzielnikiem \( a \) lub, że \( a \) jest wielokrotnością \( b \). Innymi słowy, jeśli \( b \) dzieli \( a \) to reszta z dzielenia \( a \) przez \( b \) równa jest \( 0 \) tzn. \( a\ {\sf mod} \ b =0 \).
Obserwacja 10.1
Dla dowolnych \( a,b,c \) zachodzi:
Dowód
Z założenia pierwszego punktu wiemy, iż istnieje \( d \) takie, że \( ad=b \). Mnożąc obie strony równości przez \( c \) dostajemy \( adc=bc \). A więc istnieje \( d'=dc \) takie, że \( ad'=bc \), co z kolei oznacza, że \( a|bc \).
Z założenia drugiego punktu wiemy, iż istnieją \( d,e\in\mathbb{Z} \) takie, że \( ad=b \) i \( be=c \). Łatwo zauważamy, że dla \( d'=de \) mamy \( ad'=c \), czyli \( a|c \).
Z założenia trzeciego punktu istnieją \( d,e \) takie, że \( ad=b \) i \( ae=c \). Dodając stronami ostatnie równości otrzymujemy \( a(d+e)=b+c \), czyli \( a|b+c \).
Największy wspólny dzielnik liczb \( a \) i \( b \) (zapisywany przez \( {\sf NWD}\ (a,b) \), gdzie chociaż jedna z liczb \( a,b \) jest różna od \( 0 \), to największa liczba \( d \) taka, że \( d|a \) i \( d|b \). Oczywiście, \( 1 \leq\ {\sf NWD}\ (a,b) \leq \min (|,|) \).
Przykład
\( {\sf NWD}\ (30,75)=15 \), \( {\sf NWD}\ (10,3)=1 \), \( {\sf NWD}\ (2,8)=2 \).
Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych. Warto tu wspomnieć, iż jest to jeden z najstarszych znanych algorytmów. Euklides zamieścił go ok. 300 roku p.n.e. w Elementach - jednym z najsłynniejszych dzieł naukowych ludzkości. Jednak sam algorytm prawie na pewno znał już Eudoksos z Knidos ok. 50 lat wcześniej.
Przykład
Przebieg obliczenia \( {\sf NWD}\ (1029,1071) \):
\( \begin{array} {llll} a=1029 & b=1071 & 1029=0\cdot 1071+1029 & r=1029 \\ a=1071 & b=1029 & 1071=1\cdot 1029+42 & r=42 \\ a=1029 & b=42 & 1029=24\cdot 42+21 & r=21 \\ a=42 & b=21 & 42=2\cdot 21+0 & r=0 \\ a=21 & b=0 & & \end{array} \)
Zgodnie z instrukcją (4) algorytm zwraca \( a=21 \).
Dowód
Dla dowódu poprawności algorytmu Euklidesa ustalmy dwie liczy naturalne \( a,b>0 \). Jeśli \( a < b \) to podany algorytm odwróci ich porządek przy pierwszym wykonaniu kroku (3), gdyż w tym przypadku \( a \ {\sf mod} \ b =a \). Zauważmy, że w każdym następnym kroku \( a>b>r \), ponieważ reszta z dzielenia \( a \) przez \( b \) leży w zbiorze \( {\{ {0,\ldots,b-1} \} } \). A zatem kolejne reszty będą tworzyć ciąg ściśle malejący, który w końcu osiągnie \( 0 \), czyli algorytm Euklidesa po pewnej skończonej ilości kroków się zatrzyma.
Pozostaje sprawdzić, czy algorytm Euklidesa zwraca właściwą odpowiedź. Niech \( r=a \ {\sf mod} \ b \) tzn. \( r=a-bq \) dla pewnego \( q \). Wszystkie dzielniki \( a \) i \( b \) dzielą prawą stronę ostatniej równości, a więc dzielą też \( r \), co implikuje \( {\sf NWD}\ (a,b)={\sf NWD}\ (b,r) \). Dowodzi to, iż wszystkie pary rozważane przez algorytm mają te same dzielniki, a więc ten sam \( {\sf NWD } \).
Poza znajdowaniem NWD dwóch podanych liczb \( a,b>0 \) algorytm Euklidesa można zastosować do wskazania dwu dodatkowych liczb \( x,y\in\mathbb{Z} \) takich, że
\( ax+by={\sf NWD}\ (a,b). \)
Już sam fakt, że istnieją takie liczby \( x,y \) to obserwacja, która leży u podstaw wielu kolejnych twierdzeń. Ponadto rozszerzony algorytm Euklidesa jest intensywnie stosowany do rozwiązywania równań, w przekształceniach kryptograficznych.
Dowód
Załóżmy, że \( a>b \). Niech \( r_0=a \), \( r_1=b \), natomiast \( r_2\ldots,r_n,r_{n+1} \) będą kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym \( r_{n+1}=0 \). Wtedy wiemy, że \( r_n={\sf NWD}\ (a,b) \) oraz
\( \begin{align*} {} r_{n-1} & =q_{n-1}\cdot r_n, \\ r_{n-2} & =q_{n-2}\cdot r_{n-1} + r_n, \\ r_{n-3} & =q_{n-3}\cdot r_{n-2} + r_{n-1}, \\ & \vdots & \\ r_1 & =q_1\cdot r_2+r_3, \\ r_0 & =q_0\cdot r_1+r_2, \end{align*} \)
dla pewnych \( q_0,q_1,\ldots,q_{n-1} \). Mamy zatem \( r_{n-2}-q_{n-2}\cdot r_{n-1}={\sf NWD}\ (a,b) \). Załóżmy indukcyjnie, dla \( 0 < i\leq n-2 \), że istnieją \( x,y\in\mathbb{Z} \) takie, że \( r_{i}\cdot x+r_{i+1}\cdot y={\sf NWD}\ (a,b) \). Ponieważ \( r_{i+1}=r_{i-1}+q_{i-1}\cdot r_i \) otrzymujemy:
\( \begin{align*} {\sf NWD}\ (a,b) & =r_{i}\cdot x+r_{i+1}\cdot y \\ & =r_{i}\cdot x + (r_{i-1}+q_{i-1}\cdot r_i)\cdot y \\ & =r_{i-1}\cdot y+r_{i}\cdot(x+q_{i-1}\cdot y). \end{align*} \)
A więc możemy zejść z liczbą \( i \) do \( i=0 \), co daje pożądane przedstawienie \( {\sf NWD}\ (a,b) \) jako \( r_0\cdot x + r_1\cdot y =ax+by \).
Niech \( r_0,r_1,\ldots,r_{n+1} \) będą zdefiniowane, jak w dowodzie powyżej. Załóżmy dodatkowo, iż \( a>b \) (jeśli nie, to zaczynamy analizować po pierwszym kroku algorytmu). Pokażemy, że
\( r_{j+2} < \frac{1}{2}r_j. \)
Jeśli \( r_{j+1}\leq \frac{1}{2}r_j \), to natychmiast mamy \( r_{j+2} < r_{j+1}\leq\frac{1}{2} r_j \). Załóżmy więc, że \( r_{j+1}>\frac{1}{2}r_j \). W tym przypadku podczas dzielenia \( r_j \) przez \( r_{j+1} \) zachodzi \( r_j=1\cdot r_{j+1}+r_{j+2} \), czyli \( r_{j+2}=r_j-r_{j+1} < \frac{1}{2}r_j \).
Ponieważ po każdych, kolejnych dwu krokach rozmiar \( r_j \) spada co najmniej dwukrotnie, kroków jest \( O(\lg{a}) \). W każdym kroku przeprowadzane jest dzielenie liczb długości \( O(\lg{a}) \), a więc \( O(\lg^2{a}) \) operacji bitowych. To oznacza, iż do policzenia \( {\sf NWD}\ (a,b) \) (\( a\geq b \)) algorytmem Euklidesa wystarcza \( O(\lg^3{a}) \) operacji bitowych.
Aby policzyć współczynniki \( x \), \( y \) takie, że \( ax+by={\sf NWD}\ (a,b) \), zgodnie z przedstawionym dowodem, należy przedstawić \({\sf NWD}\ (a,b) \) jako kombinację \( r_{n-1} \) i \( r_{n-2} \), a później pozbyć się kolejnych \( r_i \) (poczynając od \( r_{n-1} \)) wprowadzając \( r_{i-2} \). Mamy więc \( O(\lg{a}) \) kroków i w każdym kroku przeprowadzamy mnożenie i dodawanie lub odejmowanie liczb o długości co najwyżej \( O(\lg{a}) \).
Przykład
Działanie rozszerzonego algorytmu Euklidesa dla \( a=1547 \) i \( b=560 \).
\( \begin{align*} 1547 & =2\cdot560+427 \\ 560 & =1\cdot427+133 \\ 427 & =3\cdot133+28 \\ 133 & =4\cdot28+21 \\ 28 & =1\cdot21+7 \\ 21 & =3\cdot7+0. \end{align*} \)
A więc \( {\sf NWD}\ (1547,560)=7 \). Aby wyrazić \( 7 \) jako kombinację danych wejściowych liczymy:
\( \begin{align*} 7 & =\textbf{28}-1\cdot\textbf{21}=28-1\cdot(133-4\cdot28) \\ & =-1\cdot\textbf{133}+5\cdot\textbf{28}=-1\cdot133+5\cdot(427-3\cdot133) \\ & =5\cdot\textbf{427}-16\cdot\textbf{133}=5\cdot427-16\cdot(560-1\cdot427) \\ & =-16\cdot\textbf{560}+21\cdot\textbf{427}=-16\cdot560+21\cdot(1547-2\cdot560) \\ & =21\cdot\textbf{1547}-58\cdot\textbf{560}. \end{align*} \)
Każda liczba \( b>1 \) ma przynajmniej dwa dodatnie dzielniki: \( 1 \) oraz \( b \).
Liczba pierwsza to liczba naturalna \( p \) posiadająca dokładnie dwa różne dzielniki. W szczególności \( p>1 \).
Przykład
Oto lista wszystkich liczb pierwszych mniejszych od \( 100 \):
\( 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. \)
Liczba złożona to liczba naturalna \( a \), która nie jest pierwsza, a więc ma jakiś dodatni dzielnik różny od \( 1 \) i \( a \).
Liczby względnie pierwsze to takie liczby \( a \) i \( b \), dla których \( {\sf NWD}\ (a,b)=1 \), co zapisujemy inaczej jako \( a\perp b \).
Przykład
Wspomniane Elementy Euklidesa zawierają słynny lemat:
Lemat 10.2 [Lemat Euklidesa]
Jeśli \( n|ab \) i \( n\perp a \), to \( n|b \).
Dowód
Ponieważ \( {\sf NWD}\ (a,n)=1 \), to istnieją \( x,y \) takie, że \( xa+yn=1 \). Mnożąc obie strony równości przez \( b \) otrzymujemy:
\( xab+ynb=b. \)
Z założenia wiemy, iż \( n \) dzieli lewą stronę powyższej równości. Musi zatem dzielić też prawą.
Obserwacja 10.3 [Rozkład na iloczyn liczb pierwszych]
Każdą liczbę \( n>1 \) można przedstawić jako iloczyn liczb pierwszych.
Dowód
Intuicyjnie, wystarczy rozkładać liczby złożone w iloczynie, aż wszystkie będą liczbami pierwszymi, na przykład
\( 168=28\cdot6=(4\cdot7)\cdot(2\cdot3)=(2\cdot2)\cdot7\cdot2\cdot3. \)
Dla formalnego dowodu załóżmy niewprost, iż istnieje liczba naturalna większa od \( 1 \), nierozkładalna na iloczyn liczb pierwszych. Korzystając z Zasady Minimum, weźmy najmniejszą taką liczbę \( n \). Musi to być liczba złożona, gdyż dowolna liczba pierwsza jest jednoelementowym iloczynem liczb pierwszych. A zatem \( n \) jest złożona i istnieją \( a,b>1 \) takie, że \( n=ab \). Ale wtedy \( a \) oraz \( b \) są mniejsze od \( n \), więc z minimalności \( n \), rozkładają się na iloczyn liczb pierwszych. Ale wtedy także \( n=ab \) byłoby iloczynem liczb pierwszych, co przeczy temu, że \( n \) jest nierozkładalna i kończy dowód.
Nietrywialnym faktem jest, że każda liczba \( n>1 \) jest jednoznacznie rozkładalna na iloczyn liczb pierwszych (z dokładnością do kolejności liczb w iloczynie). Fakt ten powszechnie znany jest jako Fundamentalne Twierdzenie Arytmetyki. Dowód tego twierdzenia w dużej części był już w Elementach Euklidesa, jednak pierwszy, pełny i poprawny dowód przedstawił Carl Friedrich Gauss.
Twierdzenie 10.4 [Fundamentalne Twierdzenie Arytmetyki]
Każda liczba naturalna \( n>1 \) ma jednoznaczny (z dokładnością do kolejności liczb w iloczynie) rozkład na iloczyn liczb pierwszych.
Dowód
Podamy dwa dowody tego twierdzenia.
Najpierw przedstawimy dowód pochodzący od Euklidesa. Niech \( n>1 \) będzie najmniejszą liczbą naturalną posiadającą dwa różne rozkłady na liczby pierwsze: \( p_1\ldots p_k=n=q_1\ldots q_m \), gdzie \( p_1\leq\ldots\leq p_k \) oraz \( q_1\leq\ldots\leq q_m \). Żadna z liczb \( p_i \) nie może pojawić wśród \( q_1,\ldots,q_m \) (i na odwrót), gdyż wydzielając obie strony przez \( p_i \), otrzymalibyśmy mniejszą liczbę z dwoma różnymi rozkładami. Liczba pierwsza \( p_1 \) dzieli pierwszy iloczyn, a więc też dzieli i drugi:
\( p_1|q_1\ldots q_m. \)
Zauważmy, że
\( p_1\perp q_1, \)
gdyż są to dwie, różne liczby pierwsze. Na mocy Lematu Euklidesa otrzymujemy, iż \( p_1|q_2\ldots q_m \). Kolejno możemy wyeliminować pozostałe liczby \( q_i \) z prawego iloczynu dochodząc do \( p_1|1 \), oczywistej sprzeczności.
A oto alternatywny dowód. Niech \( n \) będzie najmniejszą liczbą naturalną większą od \( 1 \) posiadającą dwa różne rozkłady na liczby pierwsze: \( p_1\ldots p_k=n=q_1\ldots q_m \), gdzie \( p_1\leq\ldots\leq p_k \) oraz \( q_1\leq\ldots\leq q_m \). Tak, jak poprzednio dostajemy, że żadna liczba pierwsza nie może być jednocześnie w obu rozkładach. Bez straty ogólności niech \( p_1 < q_1 \). Wtedy istnieje \( d,r\in\mathbb{Z} \) takie, że
\( q_1/p_1=d+r/p_1, \)
gdzie \( 0 < r < p_1 < q_1 \) (\( r \) nie może być równe \( 0 \), gdyż oznaczałoby to iż \( p_1|q_1 \)). Wymnażając obie strony równości przez \( q_2\ldots q_m \) otrzymujemy
\( p_2\ldots p_k=dq_2\ldots q_m+rq_2\ldots q_m/p_1. \)
Drugi składnik w prawej stronie tej równości musi być zatem liczbą naturalną. Oznaczając ją przez \( x \) mamy więc
\( xp_1=rq_2\ldots q_m. \)
Wartość obu stron powyższej równości jest mniejsza od \( n \), gdyż \( r < q_1 \). Ponieważ \( r < p_1 \), to po rozłożeniu liczby \( x \) na czynniki pierwsze dostaniemy dwa różne rozkłady liczby mniejszej od \( n \), co przeczy założeniu o minimalności \( n \).
Fundamentalne Twierdzenie Arytmetyki eksponuje znaczenie liczb pierwszych. Okazuje się, że są to podstawowe bloki, z których można zbudować w unikalny sposób dowolną liczbę naturalną większą od \( 1 \).
Przykład
\( 1925=5^2\cdot7\cdot11 \), \( 2006=2\cdot17\cdot59 \), \( 108=2^2\cdot3^3 \), \( 2048=2^{11} \).
Obecnie nie jest znany żaden efektywny algorytm faktoryzujący liczby naturalne, tzn. znajdujący rozkład na iloczyn liczb pierwszych. Oczekiwana trudność tego problemu jest sercem wielu współczesnych systemów kryptograficznych (np. RSA). Nie wszystkie liczby są równie trudne w rozkładzie. Póki co, (w połowie 2006 roku) najtrudniejsze wydają się liczby, które są iloczynami dwu liczb pierwszych podobnej długości.
Przykład
Aby choć trochę zrozumieć trudność problemu faktoryzacji proponujemy znaleźć nietrywialny dzielnik liczby złożonej \( 10721 \). Na stronie WWW firmy RSA podane są znacznie większe liczby, za rozkład których RSA skłonna jest płacić nawet 200 tys. USD.
Znajomość rozkładu liczby na czynniki pierwsze pozwala określić, w sposób systematyczny, wszystkie jej dzielniki.
Obserwacja 10.5
Jeśli \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) jest rozkładem liczby \( n \) na iloczyn liczb pierwszych, to każdy jej dzielnik \( d|n \) jest postaci \( d=p_{1}^{\beta_{1}}\ldots p_{k}^{\beta_{k}} \), dla pewnych \( 0\leq\beta_i\leq\alpha_i \).
Dowód
Załóżmy, dla dowodu niewprost, że w rozkładzie liczby \( d \) występuje liczba pierwsza, powiedzmy \( p \), która nie występuje w rozkładzie \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \). Oczywiście \( p|n \), bo \( d|n \). Ponieważ \( p \) i \( p_1 \) są dwiema różnymi liczbami pierwszymi, to na mocy Lematu Euklidesa otrzymujemy \( p|p_2^{\alpha_2}\ldots p_k^{\alpha_k} \). W podobny sposób możemy wyeliminować kolejno liczby \( p_2,\ldots,p_k \) dochodząc do sprzeczności, że \( p|1 \). A więc rozkład liczby \( d \) zawiera wyłącznie liczby pierwsze z rozkładu liczby\( n \), czyli \( d=p_1^{\beta_1}\ldots p_k^{\beta_k} \), przy czym oczywiście wszystkie \( \beta_i \) są nieujemne, ale niektóre mogą być zerowe. Pozostaje pokazać, że \( \beta_i\leq\alpha_i \). Załóżmy, że \( \beta_{i}>\alpha_{i} \) dla pewnego \( i \). Wtedy
\( \frac{d}{p_i^{\alpha_{i}}} \mbox{ \ dzieli \ } \frac{n}{p_i^{\alpha_{i}}}, \)
przy czym liczba \( \frac{d}{p_i^{\alpha_{i}}} \) ma w swoim rozkładzie czynnik \( p_{i} \), a liczba \( \frac{n}{p_i^{\alpha_{i}}} \) nie ma. To jednak stoi w sprzeczności z ustanowionym wcześniej faktem, że wszystkie czynniki rozkładu każdego dzielnika jakiejkolwiek liczby naturalnej występują w rozkładzie tego dzielnika.
Ponieważ ciągów liczb naturalnych \( (\beta_1,\ldots,\beta_k) \) spełniających \( 0\leq\beta_i\leq\alpha_i \) jest dokładnie \( (\alpha_1+1)\cdot(\alpha_2+1)\cdot\ldots\cdot(\alpha_k+1) \) z Obserwacji 10.5 dostajemy natychmiast:
Wniosek 10.6
Jeśli \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) jest rozkładem liczby \( n \) na iloczyn liczb pierwszych, to liczba \( n \) ma dokładnie \( (\alpha_1+1)\cdot(\alpha_2+1)\cdot\ldots\cdot(\alpha_k+1) \) dodatnich dzielników.
Przykład
Innym natychmiastowym wnioskiem z Obserwacji 10.5 jest:
Wniosek 10.7
Dla \( a,b,c\in\mathbb{N} \) jeśli \( a|c \), \( b|c \) i \( a\perp b \), to \( ab|c \).
Mając dany rozkład liczb \( a \) i \( b \) możemy błyskawicznie policzyć \( {\sf NWD}\ (a,b) \).
Obserwacja 10.8
Jeśli \( a,b>0 \), \( a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) i \( b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k} \), gdzie \( \alpha_i, \beta_i \geq 0 \), to
\( {\sf NWD}\ (a,b)=p_1^{\min(\alpha_1,\beta_1)}\cdot \ldots\cdot p_k^{\min(\alpha_k,\beta_k)}. \)
Dowód
Każdy wspólny dzielnik \( d|a,b \) jest postaci \( d=p_1^{\gamma_1}p_2^{\gamma_2}\ldots p_k^{\gamma_k} \), przy czym \( \gamma_i\leq\alpha_i \) oraz \( \gamma_i\leq\beta_i \). Oczywiście wśród liczb tej postaci, liczba \( p_1^{\min(\alpha_1,\beta_1)}\cdot \ldots\cdot p_k^{\min(\alpha_k,\beta_k)} \) jest największa.
Oczywiście mając rozkłady liczb \( a,b \) na czynniki pierwsze łatwo jest już policzyć \( {\sf NWD}\ (a,b) \). Jak jednak odnotowaliśmy uzyskanie takich rozkładów nie jest łatwe. Dzięki algorytmowi Euklidesa potrafimy jednak (efektywnie) znaleźć NWD dwóch liczb bez znajomości ich rozkładu.
Ważnym dualnym pojęciem do NWD jest pojęcie najmniejszej wspólnej wielokrotności dwu liczb.
Najmniejsza wspólna wielokrotność dwu liczb \( a,b>0 \) (oznaczana przez \( {\sf NWW}\ (a,b) \)) to najmniejsza liczba dodatnia \( w \) taka, że \( a|w \) i \( b|w \).
Znając rozkłady dwu liczb możemy, analogicznie do NWD , wyznaczyć ich NWW.
Obserwacja 10.9
Jeśli \( a,b>0 \), \( a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) i \( b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k} \), gdzie \( \alpha_i, \beta_i \geq 0 \), to
\( {\sf NWW}\ (a,b)=p_1^{\max(\alpha_1,\beta_1)}\cdot \ldots\cdot p_k^{\max(\alpha_k,\beta_k)}. \)
Na podstawie ostatnich dwu obserwacji dostajemy natychmiast:
Wniosek 10.10
\( {\sf NWD} \ (a,b) \cdot {\sf NWW} \ (a,b)=ab. \)
Wniosek ten można wykorzystać do szybkiego liczenia NWD dwu liczb bez znajomości ich rozkładów na czynniki pierwsze. Wyznaczywszy najpierw algorytmem Euklidesa wartość \( {\sf NWD}\ (a,b) \), wystarczy potem podzielić
\( {\sf NWW}\ (a,b)= \frac{a\cdot b}{ {\sf NWD}\ (a,b)}. \)
Już Euklides odnotował, że "jest więcej liczb pierwszych niż w każdym danym zbiorze liczb pierwszych", tzn.:
Twierdzenie 10.11
Liczb pierwszych jest nieskończenie wiele.
Dowód
Podamy dwa dowody tego twierdzenia pochodzące odpowiednio od Euklidesa i Eulera.
Załóżmy niewprost za Euklidesem, że liczb pierwszych jest skończenie wiele i są to: \( p_1,\ldots,p_k \). Rozważmy liczbę \( n=p_1p_2\ldots p_k+1 \). Jest ona oczywiście większa od każdej \( p_i \). Ponadto żadna z liczb pierwszych \( p_i \) nie dzieli \( n \), bo przy dzieleniu przez \( p_i \) daje resztę \( 1 \). A zatem \( n \), albo jest nową liczbą pierwszą, albo w rozkładzie \( n \) są nowe liczby pierwsze. Sprzeczność.
Również dowód Eulera jest dowodem niewprost. Załóżmy więc, że zbiór \( \mathbb{P} \) wszystkich liczb pierwszych jest skończony. Zauważmy, że:
\( \displaystyle \prod_{p\in\mathbb{P}}\frac{1}{1-\frac{1}{p}} =\prod_{p\in\mathbb{P}}(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\ldots) =\sum_{n\geq1}\frac{1}{n}. \)
Istotnie, pierwsza równość wynika ze wzoru na sumę nieskończonego ciągu geometrycznego: każdy czynnik iloczynu po lewej jest sumą nieskończonego ciągu geometrycznego o ilorazie \( \frac{1}{p} \). Druga równość jest konsekwencją Fundamentalnego Twierdzenia Arytmetyki. Ponieważ założyliśmy, że liczb pierwszych jest skończenie wiele, to lewa strona równości jest oczywiście skończona. Wiemy natomiast, że suma po prawej stronie jest nieograniczona, jako że sumy częściowe początkowych \( n \) wyrazów tego ciągu to kolejne liczby harmoniczne \( H_n\geq \frac{\lfloor \lg{n}\rfloor+1}{2} \).
Matematycy zastanawiali się także, czy liczby pierwsze są, w pewnym sensie, regularnie rozłożone wśród liczb naturalnych. Jest wiele ciekawych rezultatów opisujących ten rozkład.
Twierdzenie 10.12 [Dirichlet 1837]
Dla dowolnych dwu dodatnich i względnie pierwszych liczb \( a,d \) istnieje nieskończenie wiele liczb postaci \( nd+a \) dla \( n>0 \).
Przykład
Twierdzenie Dirichleta uogólnia wiele wcześniej znanych faktów. Dla przykładu, możemy wywnioskować, iż jest nieskończenie wiele liczb pierwszych postaci \( 4n+1 \) (\( d=4,a=1 \)):
\( \begin{array} {|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline 4n+1 & 1 & \bf 5 & 9 & 13 & \bf 17 & 21 & 25 & \bf 29 & 33 & \bf 37 & \bf 41 & 45 & 49 \\ \hline \end {array} \)
jak i postaci \( 4n+3 \) (\( d=4, a=3 \)):
\( \begin{array} {|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline 4n+3 & \bf 3 & \bf 7 & \bf 11 & 15 & \bf 19 & \bf 23 & 27 & \bf 31 & 35 & 39 & \bf 43 & \bf 47 & 51 \\ \hline \end {array} \)
Tezę kolejnego twierdzenia, znanego jako Twierdzenie Bertanda-Czebyszewa lub Twierdzenie Czebyszewa, postawił Joseph Bertrand w 1845 roku. Zweryfikował on poprawność swojej tezy dla liczb \( n \) z przedziału \( [2,\ldots,3\cdot10^6] \). Pełny dowód przestawił dopiero Pafnuty Czebyszew w 1850 roku. Dowód, który tu przedstawiamy pochodzi od Paula Erd{o}s'a. Wykorzystał on następującą funkcję
\( \displaystyle \vartheta(n)=\sum_{p\in\mathbb{P}_n}\ln{p}, \)
gdzie \( \mathbb{P}_n \) oznacza zbiór liczb pierwszych nie większych od \( n \). Ważną własność tej funkcji opisuje następujący lemat.
Lemat 10.13
Dla \( n\geq 1 \) zachodzi
\( \vartheta(n) < n\cdot\ln{4}. \)
Dowód
Dla dowodu indukcyjnego odnotujmy najpierw, że \( \vartheta(1)=0 < 1\cdot\ln{4} \) oraz \( \vartheta(2)=\ln{2} < 2\cdot\ln{4} \).
Niech teraz \( n>2 \) będzie parzyste. Wtedy oczywiście \( n \) nie jest liczbą pierwszą i mamy
\( \vartheta(n)=\vartheta(n-1) < (n-1)\cdot\ln{4} < n\cdot\ln{4}. \)
Niech więc \( n>2 \) będzie nieparzyste, czyli \( n=2m+1 \) dla pewnego \( m>0 \). Rozważmy liczbę
\( {2m+1\choose m}=\frac{(2m)!}{m!\cdot m!}. \)
Zauważmy, że każda liczba pierwsza \( p \) w przedziale \( m < p\leq 2m+1 \) dzieli \( {2m+1\choose m} \). Rzeczywiście, żadna liczba z mianownika nie może skrócić liczby pierwszej \( p \) w liczniku co oznacza, że \( p \) jest w rozkładzie \( {2m+1\choose m} \). Ponadto, łatwo oszacować \( {2m+1\choose m} \) od góry przez \( 4^m \), np. w ten sposób:
\( \displaystyle 4^m=\frac{(1+1)^{2m+1}}{2} =\frac{\sum_{k=0}^{2m+1}{2m+1\choose k}}{2} \geq\frac{{2m+1\choose m}+{2m+1\choose m+1}}{2} ={2m+1\choose m}. \)
To z kolei pozwala nam oszacować \( \vartheta(2m+1) \) następująco:
\( \displaystyle \vartheta(2m+1)-\vartheta(m+1) =\sum_{p\in\mathbb{P}_{2m+1}-\mathbb{P}_{m+1}}\ln{p} \leq\ln{{2m+1\choose m}} \leq\ln{4^m} \leq m\cdot\ln{4}. \)
Z założenia indukcyjnego mamy natomiast \( \vartheta(m+1) < m\cdot\ln{4} \), czyli
\( \vartheta(n)=\vartheta(2m+1) < m\cdot\ln{4}+(m+1)\cdot\ln{4}=n\cdot\ln{4}. \)
Twierdzenie 10.14 [Czebyszew 1850]
Dla dowolnego \( n>1 \) istnieje liczba pierwsza \( p \) taka, że \( n < p < 2n \).
Dowód
Dla dowodu niewprost załóżmy, że \( n \) jest najmniejszą liczbą \( n\geq 2 \), dla której nie ma żadnej liczby pierwszej \( p \) w przedziale \( n < p < 2n \). Jeśli \( 2\leq n\leq 2048 \), to jedna z liczb pierwszych \( 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503 \) będzie pomiędzy \( n \) a \( 2n \). Oznacza to, że \( n\geq2048 \).
Przeanalizujmy teraz rozkład na czynniki pierwsze liczby:
\( {2n\choose n}=\frac{(2n)!}{n!\cdot n!}. \)
Najpierw jednak zauważmy, że ponieważ \( \displaystyle 4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n\choose k} \) a liczba \( {2n\choose n} \) jest największym składnikiem tej sumy, to:
\( \frac{4^n}{2n+1}\leq{2n\choose n}. \)
Ponieważ \( 2n \) jest największym czynnikiem licznika \( \frac{(2n)!}{n!\cdot n!}={2n\choose n} \), to wszystkie liczby pierwsze \( p \) w rozkładzie \( 2n\choose n \) są mniejsze od \( 2n \). Niech \( R(p,n) \), gdzie \( p \) jest liczbą pierwszą, będzie największą liczbą \( x \) taką, że \( p^x|{2n\choose n} \). Innymi słowy, \( R(p,n) \) jest potęgą liczby \( p \) w rozkładzie \( {2n\choose n} \).
Łatwo zauważyć, że \( n! \) ma czynnik \( p \) w swoim rozkładzie na czynniki pierwsze \( \displaystyle \sum_{k=1}^{\infty}\lfloor\frac{n}{p^k}\rfloor \) razy. To implikuje, że
\( \displaystyle R(p,n) =\sum_{k=1}^\infty\lfloor\frac{2n}{p^k}\rfloor-2\cdot\sum_{k=1}^\infty\lfloor\frac{n}{p^k}\rfloor =\sum_{k=1}^{\infty}(\lfloor\frac{2n}{p^k}\rfloor-2\lfloor\frac{n}{p^k}\rfloor). \)
Każdy składnik tej sumy postaci \( \lfloor\frac{2n}{p^k}\rfloor-2\lfloor\frac{n}{p^k}\rfloor \) może przyjąć wartość:
lub
Ponadto, dla \( k>\log_p{2n} \) wszystkie składniki zerują się, bo \( \frac{2n}{p^k} < 1 \). To pozwala na następujące oszacowanie liczby \( R(p,n) \)
\( R(p,n) < \lfloor\log_p{2n}\rfloor. \)
To z kolei daje zaskakującą nierówność
\( p^{R(p,n)}\leq 2n. \)
Z dotychczasowych ustaleń dotyczących rozkładu liczby \( {2n\choose n} \) na czynniki pierwsze wiemy, że nie występują tam liczby pierwsze \( p \) takie, że:
Zatem wszystkie liczby pierwsze w rozkładzie \( {2n\choose n} \) są niewiększe niż \( \frac{2}{3}n \). Liczby pierwsze \( p>\sqrt{2n} \) występują tam w co najwyżej pierwszej potędze, jako że \( p^{R(p,n)} < 2n \). Z kolei iloczyn \( \prod p^{R(p,n)} \) przebiegający po liczbach pierwszych \( p\leq\sqrt{2n} \) można oszacować z góry przez \( (2n)^{\sqrt{2n}} \). Dotychczasowe oszacowania dają nam więc
\( \displaystyle \frac{4^n}{2n+1}\leq{2n\choose n}\leq(2n)^{\sqrt{2n}}\prod_{p\in\mathbb{P}_{\frac{2}{3}n}}p=(2n)^{\sqrt{2n}}e^{\vartheta(\frac{2}{3}n)}. \)
Z Lematu 10.13 wiemy, że \( \vartheta(n) < n\cdot\ln{4} \), więc
\( \frac{4^n}{2n+1}\leq(2n)^{\sqrt{2n}}4^{\frac{2}{3}n}. \)
Ponieważ \( 2n+1 < (2n)^2 \) mamy
\( 4^{\frac{n}{3}} < (2n)^{2+\sqrt{2n}}. \)
Z kolei \( 2\leq\frac{\sqrt{2n}}{3} \), bo \( n\geq18 \), więc
\( 4^{\frac{n}{3}}\leq(2n)^{\frac{4}{3}\sqrt{2n}}. \)
Logarytmując obie strony nierówności otrzymujemy
\( \sqrt{2n}\leq 4\cdot\lg{(2n)}. \)
Podstawmy \( n=2^{2t-1} \). Wtedy \( \frac{2^t}{t}\leq 4 \), a więc \( t < 6 \), co w stoi sprzeczności z \( n>2048 \), gdyż
\( n=\frac{2^{2t}}{2} < \frac{2^{2\cdot6}}{2}=2048. \)
Paulowi Erd{o}s'owi udało się uogólnić Twierdzenie Bertranda-Czebyszewa na kilka sposobów. Pokazał on np., że:
Wszystkie obserwacje o pewnej regularności rozkładu liczb pierwszych w zbiorze liczb naturalnych potwierdza (i w pewnym sensie uogólnia) Twierdzenie o Liczbach Pierwszych. Niech, jak poprzednio, \( \mathbb{P}_n \) będzie zbiorem liczb pierwszych niewiększych od \( n \) oraz \( \pi(n)=\vert\mathbb{P}_n\vert \).
Twierdzenie 10.15 [Twierdzenie o Liczbach Pierwszych]
\( \pi(n)\sim n/\ln{n}. \)
Twierdzenie o Liczbach Pierwszych opisuje asymptotyczną gęstość liczb pierwszych wśród liczb naturalnych. Z grubsza, mówi ono, iż wybierając losowo liczbę w pobliżu pewnej dużej liczby \( n \), mamy \( \frac{1}{\ln{n}} \) szansy na to, by wylosowana liczba była pierwsza. Dla przykładu: w pobliżu \( n=10 000 \) mniej więcej co \( 9 \)-ta liczba jest pierwsza, tymczasem w pobliżu \( n=1 000 000 000 \) już co \( 21 \)-wsza liczba jest pierwsza. A więc, statystycznie, w przedziale \( (n,2n) \) jest znacznie więcej liczb pierwszych niż mówią poprzednie twierdzenia. Problem polega na tym, że choć wiemy, że musi ich być bardzo dużo, to nie jesteśmy w stanie udowodnić, że dla konkretnie rozważanej liczby \( n \) nie nastąpiło jakieś "lokalne zaburzenie".
Twierdzenie o Liczbach Pierwszych sformułował Adrien-Marie Legendre'a w 1796. Zostało ono udowodnione niezależnie przez Hadamarda i de la Vallée Poussina w 1896. Dowód używa złożonych metod analitycznych, wykraczających poza ramy tego wykładu. Dlatego nie przedstawimy jego pełnego dowodu. W zamian pokażemy znacznie słabsze:
Twierdzenie 10.16
\( \pi(n)=O(n/\ln{n}) \).
Dowód
Lemat 10.13 mówi, że \( \vartheta(n) < n\cdot\ln{4} \), co równoważnie można wyrazić jako
\( \displaystyle \prod_{p\in\mathbb{P}_n} < 4^n. \)
Ponieważ w oczywisty sposób \( \displaystyle \pi(n)!\leq \prod_{p\in\mathbb{P}_n} \), to ze wzoru Stirlinga mamy:
\( \displaystyle (\frac{\pi(n)}{e})^{\pi(n)} < (\pi(n))! < \prod_{p\in\mathbb{P}_n}p < 4^n. \)
Logarytmując stronami otrzymujemy \( \pi(n)\cdot(\ln{\pi(n)}-1) < n\cdot\ln{4} \), co implikuje \( \pi(n)=O(n/\ln{n}) \).
Jak wyznaczyć wszystkie \( \pi(200) \) liczb pierwszych niewiększych od \( 200 \)? Jeszcze w czasach starożytnych Eratostenes opisał metodę postępowania rozwiązującą ten problem.
Wystarczy wykreślać wielokrotności liczb pierwszych, niewiększych od \( \sqrt{n} \), gdyż jeśli dowolna liczba \( m\leq n \) ma nietrywialny dzielnik (różny od 1 i niej samej), to \( m \) ma nietrywialny dzielnik pierwszy, niewiększy od \( \sqrt{n} \).