Matematyka dyskretna 1/Wykład 10: Teoria liczb

From Studia Informatyczne

Spis treści

Wstęp

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 \left\lfloor \lg{n}\right\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).

Podstawowe pojęcia

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ą.

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 \mbox{ {\sf mod} } b.

Przykład

47 \mbox{ {\sf mod} } 9 =2, 1823 \mbox{ {\sf mod} } 2 =1, 32 \mbox{ {\sf mod} } 43 =32, 111 \mbox{ {\sf mod} } 13 =7, -3 \mbox{ {\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 \mbox{ {\sf mod} } b =0.

Obserwacja 10.1

Dla dowolnych a,b,c zachodzi:

  • jeśli a|b to a|bc,
  • jeśli a|b i b|c to a|c,
  • jeśli a|b, a|c to a|(b+c).

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.

image:End_of_proof.gif

Największy wspólny dzielnik liczb a i b (zapisywany przez \mbox{\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\leqslant\mbox{\sf NWD}(a,b)\leq \min(\left\verta\right\vert,\left\vertb\right\vert).

Przykład

\mbox{\sf NWD}(30,75)=15, \mbox{\sf NWD}(10,3)=1, \mbox{\sf NWD}(2,8)=2.

Algorytm Euklidesa

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.

  1. Wczytaj liczby a,b>0.
  2. Oblicz r jako resztę z dzielenia a przez b.
  3. Zastąp a przez b, zaś b przez r.
  4. Jeżeli b=0 to zwróć a w przeciwnym wypadku przejdź do (2).

Przykład

Przebieg obliczenia \mbox{\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 \mbox{ {\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 {\left\{ {0,\ldots,b-1} \right\} }. 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 \mbox{ {\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 \mbox{\sf NWD}(a,b)=\mbox{\sf NWD}(b,r). Dowodzi to, iż wszystkie pary rozważane przez algorytm mają te same dzielniki, a więc ten sam \mbox{\sf NWD }.

image:End_of_proof.gif

Rozszerzenie algorytmu Euklidesa.

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=\mbox{\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=\mbox{\sf NWD}(a,b) oraz


\aligned {} 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, \endaligned


dla pewnych q_0,q_1,\ldots,q_{n-1}. Mamy zatem r_{n-2}-q_{n-2}\cdot r_{n-1}=\mbox{\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=\mbox{\sf NWD}(a,b). Ponieważ r_{i+1}=r_{i-1}+q_{i-1}\cdot r_i otrzymujemy:


\aligned \mbox{\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). \endaligned


A więc możemy zejść z liczbą i do i=0, co daje pożądane przedstawienie \mbox{\sf NWD}(a,b) jako r_0\cdot x + r_1\cdot y =ax+by.

image:End_of_proof.gif

Czas działania.

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}\leqslant\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 \mbox{\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=\mbox{\sf NWD}(a,b), zgodnie z przedstawionym dowodem, należy przedstawić \mbox{\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.


\aligned 1547&=2\cdot560+427\\ 560&=1\cdot427+133\\ 427&=3\cdot133+28\\ 133&=4\cdot28+21\\ 28&=1\cdot21+7\\ 21&=3\cdot7+0. \endaligned


A więc \mbox{\sf NWD}(1547,560)=7. Aby wyrazić 7 jako kombinację danych wejściowych liczymy:


\aligned 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}. \endaligned




Liczby pierwsze

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 \mbox{\sf NWD}(a,b)=1, co zapisujemy inaczej jako a\perp b.

Przykład

  • 10\perp 3 bo \mbox{\sf NWD}(10,3)=1,
  • 12\not\perp 3 bo \mbox{\sf NWD}(12,3)=3,
  • 7\perp 15 bo \mbox{\sf NWD}(7,15)=1.

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ż \mbox{\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ą.

image:End_of_proof.gif

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.

image:End_of_proof.gif

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\leqslant\ldots\leq p_k oraz q_1\leqslant\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\leqslant\ldots\leq p_k oraz q_1\leqslant\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.

image:End_of_proof.gif

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}.

Problem faktoryzacji.

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\leqslant\beta_i\leqslant\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 liczbyn, 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\leqslant\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.

image:End_of_proof.gif

Ponieważ ciągów liczb naturalnych (\beta_1,\ldots,\beta_k) spełniających 0\leqslant\beta_i\leqslant\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ć \mbox{\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


\mbox{\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\leqslant\alpha_i oraz \gamma_i\leqslant\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.

image:End_of_proof.gif

Oczywiście mając rozkłady liczb a,b na czynniki pierwsze łatwo jest już policzyć \mbox{\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 \mbox{\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


\mbox{\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

\mbox{\sf NWD}(a,b)\cdot\mbox{\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ść \mbox{\sf NWD}(a,b), wystarczy potem podzielić


\mbox{\sf NWW}(a,b)= \frac{a\cdot b}{\mbox{\sf NWD}(a,b)}.

Jak dużo jest liczb pierwszych?

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}}\left(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\ldots\right) =\sum_{n\geqslant1}\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{\left\lfloor \lg{n}\right\rfloor+1}{2}.

image:End_of_proof.gif

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 \endarray


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 \endarray


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} \geqslant\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} \leqslant\ln{{2m+1\choose m}} \leqslant\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}.


image:End_of_proof.gif

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\geqslant2048.

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}\leqslant{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}\left\lfloor\frac{n}{p^k}\right\rfloor razy. To implikuje, że


\displaystyle R(p,n) =\sum_{k=1}^\infty\left\lfloor\frac{2n}{p^k}\right\rfloor-2\cdot\sum_{k=1}^\infty\left\lfloor\frac{n}{p^k}\right\rfloor =\sum_{k=1}^{\infty}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right).


Każdy składnik tej sumy postaci \left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor może przyjąć wartość:

  • 0, jeśli część ułamkowa \frac{n}{p^k} jest mniejsza od \frac{1}{2},

lub

  • 1, jeśli część ułamkowa \frac{n}{p^k} jest niemniejsza od \frac{1}{2}.

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)<\left\lfloor\log_p{2n}\right\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:

  • p>2n, gdyż 2n jest największym czynnikiem w liczniku rozważanego symbolu Newtona,
  • n<p\leq 2n, gdyż założyliśmy, że nie ma takich liczb pierwszych,
  • \frac{2}{3}n<p\leq n, gdyż wtedy p>\sqrt{2n} (ponieważ n\geqslant5) i wobec tego tylko pierwszy składnik w nieskończonej sumie wyznaczającej R(p,n) może być niezerowy. Ale wtedy i tak R(p,n)=\left\lfloor \frac{2n}{p}\right\rfloor-2\left\lfloor \frac{n}{p}\right\rfloor=2-2=0.

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\leqslant\sqrt{2n} można oszacować z góry przez (2n)^{\sqrt{2n}}. Dotychczasowe oszacowania dają nam więc


\displaystyle \frac{4^n}{2n+1}\leqslant{2n\choose n}\leqslant(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}\leqslant(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\leqslant\frac{\sqrt{2n}}{3}, bo n\geqslant18, więc


4^{\frac{n}{3}}\leqslant(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.


image:End_of_proof.gif

Paulowi Erd{o}s'owi udało się uogólnić Twierdzenie Bertranda-Czebyszewa na kilka sposobów. Pokazał on np., że:

  • dla każdego k istnieje takie n_0, że dla wszystkich n>n_0 istnieje przynajmniej k liczb pierwszych p_1,\ldots,p_k w przedziale n<p_i<2n,
  • dla dowolnej liczby naturalnej n>6, między liczbami n a 2n znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci 4k + 1 oraz co najmniej jedna postaci 4k + 3.

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)=\left\vert\mathbb{P}_n\right\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 \left(\frac{\pi(n)}{e}\right)^{\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}).

image:End_of_proof.gif

Sito Eratostenesa

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.

Algorytm Sita

  1. Wczytaj n. Wypisz listę wszystkich liczb naturalnych od 2 do n. Na początku wszystkie liczby są nieskreślone.
  2. Dopóki istnieje nieskreślona jeszcze liczba na naszej liście niewiększa od \sqrt{n} powtarzaj:
    Weź pierwszą nieskreśloną liczbę p z listy i dodaj do zbioru znalezionych liczb pierwszych. Później skreśl liczbę p z listy i skreśl wszystkie wielokrotności liczby p, które są jeszcze na liście.
  3. Wszystkie pozostałe, nieskreślone liczby z listy dodaj do zbioru znalezionych liczb pierwszych.

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}.