Matematyka dyskretna 1/Wykład 10: Teoria liczb

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 $\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).

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{\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\text{i}0\le r<b$

Resztę $r$ z dzielenia $a$ przez $b$ zapisujemy też jako: $a\mathsf{m}\mathsf{o}\mathsf{d}b$.

Przykład

$47\mathsf{m}\mathsf{o}\mathsf{d}9=2$, $1823\mathsf{m}\mathsf{o}\mathsf{d}2=1$, $32\mathsf{m}\mathsf{o}\mathsf{d}43=32$, $111\mathsf{m}\mathsf{o}\mathsf{d}13=7$, $-3\mathsf{m}\mathsf{o}\mathsf{d}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\mathsf{m}\mathsf{o}\mathsf{d}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^{\prime }=dc$ takie, że $a{d}^{\prime }=bc$, co z kolei oznacza, że $a|bc$.

Z założenia drugiego punktu wiemy, iż istnieją $d,e\in \mathbb{\mathbb{Z}}$ takie, że $ad=b$ i $be=c$. Łatwo zauważamy, że dla $d^{\prime }=de$ mamy $a{d}^{\prime }=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 $\mathsf{N}\mathsf{W}\mathsf{D}(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⩽\mathsf{N}\mathsf{W}\mathsf{D}(a,b)\le \min (\left|a\right|,\left|b\right|)$.

Przykład

$\mathsf{N}\mathsf{W}\mathsf{D}(30,75)=15$, $\mathsf{N}\mathsf{W}\mathsf{D}(10,3)=1$, $\mathsf{N}\mathsf{W}\mathsf{D}(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 $\mathsf{N}\mathsf{W}\mathsf{D}(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$.

Applet1

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\mathsf{m}\mathsf{o}\mathsf{d}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,\dots ,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\mathsf{m}\mathsf{o}\mathsf{d}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 $\mathsf{N}\mathsf{W}\mathsf{D}(a,b)=\mathsf{N}\mathsf{W}\mathsf{D}(b,r)$. Dowodzi to, iż wszystkie pary rozważane przez algorytm mają te same dzielniki, a więc ten sam $\mathsf{N}\mathsf{W}\mathsf{D}$.

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{\mathbb{Z}}$ takich, że

$ax+by=\mathsf{N}\mathsf{W}\mathsf{D}(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\dots ,r_n,r_{n+1}$ będą kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym $r_{n+1}=0$. Wtedy wiemy, że $r_n=\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$ oraz

$\begin{array}{rl}{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},\\ & ⋮& \\ r_1& =q_1\cdot r_2+r_3,\\ r_0& =q_0\cdot r_1+r_2,\end{array}$

dla pewnych $q_0,q_1,\dots ,q_{n-1}$. Mamy zatem $r_{n-2}-q_{n-2}\cdot r_{n-1}=\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$. Załóżmy indukcyjnie, dla $0<i\le n-2$, że istnieją $x,y\in \mathbb{\mathbb{Z}}$ takie, że $r_i\cdot x+r_{i+1}\cdot y=\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$. Ponieważ $r_{i+1}=r_{i-1}+q_{i-1}\cdot r_i$ otrzymujemy:

$\begin{array}{rl}\mathsf{N}\mathsf{W}\mathsf{D}(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{array}$

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

Czas działania.

Niech $r_0,r_1,\dots ,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}\le \frac{1}{2}{r}_j$, to natychmiast mamy $r_{j+2}<r_{j+1}⩽\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 $\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$ ($a\ge b$) algorytmem Euklidesa wystarcza $O({\lg }^{3}a)$ operacji bitowych.

Aby policzyć współczynniki $x$, $y$ takie, że $ax+by=\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$, zgodnie z przedstawionym dowodem, należy przedstawić $\mathsf{N}\mathsf{W}\mathsf{D}(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{array}{rl}1547& =2\cdot 560+427\\ 560& =1\cdot 427+133\\ 427& =3\cdot 133+28\\ 133& =4\cdot 28+21\\ 28& =1\cdot 21+7\\ 21& =3\cdot 7+0.\end{array}$

A więc $\mathsf{N}\mathsf{W}\mathsf{D}(1547,560)=7$. Aby wyrazić $7$ jako kombinację danych wejściowych liczymy:

$\begin{array}{rl}7& =\text{<mrow data-mjx-texclass="ORD"><mn>2</mn><mn>8</mn></mrow>}-1\cdot \text{<mrow data-mjx-texclass="ORD"><mn>2</mn><mn>1</mn></mrow>}=28-1\cdot (133-4\cdot 28)\\ & =-1\cdot \text{<mrow data-mjx-texclass="ORD"><mn>1</mn><mn>3</mn><mn>3</mn></mrow>}+5\cdot \text{<mrow data-mjx-texclass="ORD"><mn>2</mn><mn>8</mn></mrow>}=-1\cdot 133+5\cdot (427-3\cdot 133)\\ & =5\cdot \text{<mrow data-mjx-texclass="ORD"><mn>4</mn><mn>2</mn><mn>7</mn></mrow>}-16\cdot \text{<mrow data-mjx-texclass="ORD"><mn>1</mn><mn>3</mn><mn>3</mn></mrow>}=5\cdot 427-16\cdot (560-1\cdot 427)\\ & =-16\cdot \text{<mrow data-mjx-texclass="ORD"><mn>5</mn><mn>6</mn><mn>0</mn></mrow>}+21\cdot \text{<mrow data-mjx-texclass="ORD"><mn>4</mn><mn>2</mn><mn>7</mn></mrow>}=-16\cdot 560+21\cdot (1547-2\cdot 560)\\ & =21\cdot \text{<mrow data-mjx-texclass="ORD"><mn>1</mn><mn>5</mn><mn>4</mn><mn>7</mn></mrow>}-58\cdot \text{<mrow data-mjx-texclass="ORD"><mn>5</mn><mn>6</mn><mn>0</mn></mrow>}.\end{array}$

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 $\mathsf{N}\mathsf{W}\mathsf{D}(a,b)=1$, co zapisujemy inaczej jako $a\perp b$.

Przykład

• $10\perp 3$ bo $\mathsf{N}\mathsf{W}\mathsf{D}(10,3)=1$,
• $12\perp ̸3$ bo $\mathsf{N}\mathsf{W}\mathsf{D}(12,3)=3$,
• $7\perp 15$ bo $\mathsf{N}\mathsf{W}\mathsf{D}(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ż $\mathsf{N}\mathsf{W}\mathsf{D}(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\cdot 6=(4\cdot 7)\cdot (2\cdot 3)=(2\cdot 2)\cdot 7\cdot 2\cdot 3$

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\dots p_k=n=q_1\dots q_m$, gdzie $p_1⩽\dots \le p_k$ oraz $q_1⩽\dots \le q_m$. Żadna z liczb $p_i$ nie może pojawić wśród $q_1,\dots ,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\dots 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\dots 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\dots p_k=n=q_1\dots q_m$, gdzie $p_1⩽\dots \le p_k$ oraz $q_1⩽\dots \le 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{\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\dots q_m$ otrzymujemy

$p_2\dots p_k=d{q}_2\dots q_m+r{q}_2\dots 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

$x{p}_1=r{q}_2\dots 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\cdot 7\cdot 11$, $2006=2\cdot 17\cdot 59$, $108=2^2\cdot 3^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}\dots 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}\dots p_k^{{\beta }_k}$, dla pewnych $0⩽{\beta }_i⩽{\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}\dots 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}\dots p_k^{{\alpha }_k}$. W podobny sposób możemy wyeliminować kolejno liczby $p_2,\dots ,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}\dots p_k^{{\beta }_k}$, przy czym oczywiście wszystkie ${\beta }_i$ są nieujemne, ale niektóre mogą być zerowe. Pozostaje pokazać, że ${\beta }_i⩽{\alpha }_i$. Załóżmy, że ${\beta }_i>{\alpha }_i$ dla pewnego $i$. Wtedy

$\frac{d}{p_i^{{\alpha }_i}}\text{ 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,\dots ,{\beta }_k)$ spełniających $0⩽{\beta }_i⩽{\alpha }_i$ jest dokładnie $({\alpha }_1+1)\cdot ({\alpha }_2+1)\cdot \dots \cdot ({\alpha }_k+1)$ z Obserwacji 10.5 dostajemy natychmiast:

Wniosek 10.6

Jeśli $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots 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 \dots \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{\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ć $\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$.

Obserwacja 10.8

Jeśli $a,b>0$, $a=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$ i $b=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_k^{{\beta }_k}$, gdzie ${\alpha }_i,{\beta }_i\ge 0$, to

$\mathsf{N}\mathsf{W}\mathsf{D}(a,b)=p_1^{\min ({\alpha }_1,{\beta }_1)}\cdot \dots \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}\dots p_k^{{\gamma }_k}$, przy czym ${\gamma }_i⩽{\alpha }_i$ oraz ${\gamma }_i⩽{\beta }_i$. Oczywiście wśród liczb tej postaci, liczba $p_1^{\min ({\alpha }_1,{\beta }_1)}\cdot \dots \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ć $\mathsf{N}\mathsf{W}\mathsf{D}(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 $\mathsf{N}\mathsf{W}\mathsf{W}(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}\dots p_k^{{\alpha }_k}$ i $b=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_k^{{\beta }_k}$, gdzie ${\alpha }_i,{\beta }_i\ge 0$, to

$\mathsf{N}\mathsf{W}\mathsf{W}(a,b)=p_1^{\max ({\alpha }_1,{\beta }_1)}\cdot \dots \cdot p_k^{\max ({\alpha }_k,{\beta }_k)}$

Na podstawie ostatnich dwu obserwacji dostajemy natychmiast:

Wniosek 10.10

$\mathsf{N}\mathsf{W}\mathsf{D}(a,b)\cdot \mathsf{N}\mathsf{W}\mathsf{W}(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ść $\mathsf{N}\mathsf{W}\mathsf{D}(a,b)$, wystarczy potem podzielić

$\mathsf{N}\mathsf{W}\mathsf{W}(a,b)=\frac{a\cdot b}{\mathsf{N}\mathsf{W}\mathsf{D}(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,\dots ,p_k$. Rozważmy liczbę $n=p_1{p}_2\dots 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{\mathbb{P}}$ wszystkich liczb pierwszych jest skończony. Zauważmy, że:

$\prod _{p\in \mathbb{\mathbb{P}}}\frac{1}{1-\frac{1}{p}}=\prod _{p\in \mathbb{\mathbb{P}}}(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\dots )=\sum _{n⩾1}\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\ge \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}{cccccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ 4n+1& 1& \mathbf{𝟓}& 9& 13& \mathbf{𝟏}\mathbf{𝟕}& 21& 25& \mathbf{𝟐}\mathbf{𝟗}& 33& \mathbf{𝟑}\mathbf{𝟕}& \mathbf{𝟒}\mathbf{𝟏}& 45& 49\end{array}$

jak i postaci $4n+3$ ($d=4,a=3$):

$\begin{array}{cccccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ 4n+3& \mathbf{𝟑}& \mathbf{𝟕}& \mathbf{𝟏}\mathbf{𝟏}& 15& \mathbf{𝟏}\mathbf{𝟗}& \mathbf{𝟐}\mathbf{𝟑}& 27& \mathbf{𝟑}\mathbf{𝟏}& 35& 39& \mathbf{𝟒}\mathbf{𝟑}& \mathbf{𝟒}\mathbf{𝟕}& 51\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,\dots ,3\cdot 10^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ę

$\vartheta (n)=\sum _{p\in {\mathbb{\mathbb{P}}}_n}\ln p,$

gdzie ${\mathbb{\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\ge 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ę

$(\genfrac{}{}{0ex}{}{2m+1}{m})=\frac{(2m)!}{m!\cdot m!}$

Zauważmy, że każda liczba pierwsza $p$ w przedziale $m<p\le 2m+1$ dzieli $(\genfrac{}{}{0ex}{}{2m+1}{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 $(\genfrac{}{}{0ex}{}{2m+1}{m})$. Ponadto, łatwo oszacować $(\genfrac{}{}{0ex}{}{2m+1}{m})$ od góry przez $4^m$, np. w ten sposób:

$4^m=\frac{(1+1{)}^{2m+1}}{2}=\frac{\sum _{k=0}^{2m+1}(\genfrac{}{}{0ex}{}{2m+1}{k})}{2}⩾\frac{(\genfrac{}{}{0ex}{}{2m+1}{m})+(\genfrac{}{}{0ex}{}{2m+1}{m+1})}{2}=(\genfrac{}{}{0ex}{}{2m+1}{m})$

To z kolei pozwala nam oszacować $\vartheta (2m+1)$ następująco:

$\vartheta (2m+1)-\vartheta (m+1)=\sum _{p\in {\mathbb{\mathbb{P}}}_{2m+1}-{\mathbb{\mathbb{P}}}_{m+1}}\ln p⩽\ln (\genfrac{}{}{0ex}{}{2m+1}{m})⩽\ln 4^m\le 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\ge 2$, dla której nie ma żadnej liczby pierwszej $p$ w przedziale $n<p<2n$. Jeśli $2\le n\le 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⩾2048$.

Przeanalizujmy teraz rozkład na czynniki pierwsze liczby:

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!\cdot n!}$

Najpierw jednak zauważmy, że ponieważ $4^n=(1+1{)}^{2n}=\sum _{k=0}^{2n}(\genfrac{}{}{0ex}{}{2n}{k})$ a liczba $(\genfrac{}{}{0ex}{}{2n}{n})$ jest największym składnikiem tej sumy, to:

$\frac{4^n}{2n+1}⩽(\genfrac{}{}{0ex}{}{2n}{n})$

Ponieważ $2n$ jest największym czynnikiem licznika $\frac{(2n)!}{n!\cdot n!}=(\genfrac{}{}{0ex}{}{2n}{n})$, to wszystkie liczby pierwsze $p$ w rozkładzie $(\genfrac{}{}{0ex}{}{2n}{n})$ są mniejsze od $2n$. Niech $R(p,n)$, gdzie $p$ jest liczbą pierwszą, będzie największą liczbą $x$ taką, że $p^x|(\genfrac{}{}{0ex}{}{2n}{n})$. Innymi słowy, $R(p,n)$ jest potęgą liczby $p$ w rozkładzie $(\genfrac{}{}{0ex}{}{2n}{n})$.

Łatwo zauważyć, że $n!$ ma czynnik $p$ w swoim rozkładzie na czynniki pierwsze $\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$ razy. To implikuje, że

$R(p,n)=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{2n}{p^k}\rfloor -2\cdot \sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor =\sum _{k=1}^{\mathrm{\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ść:

• $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)<\lfloor {\log }_{p}2n\rfloor$

To z kolei daje zaskakującą nierówność

$p^{R(p,n)}\le 2n$

Z dotychczasowych ustaleń dotyczących rozkładu liczby $(\genfrac{}{}{0ex}{}{2n}{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\le 2n$, gdyż założyliśmy, że nie ma takich liczb pierwszych,

• $\frac{2}{3}n<p\le n$, gdyż wtedy $p>\sqrt{2n}$ (ponieważ $n⩾5$) 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)=\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor =2-2=0$.

Zatem wszystkie liczby pierwsze w rozkładzie $(\genfrac{}{}{0ex}{}{2n}{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⩽\sqrt{2n}$ można oszacować z góry przez $(2n{)}^{\sqrt{2n}}$. Dotychczasowe oszacowania dają nam więc

$\frac{4^n}{2n+1}⩽(\genfrac{}{}{0ex}{}{2n}{n})⩽(2n{)}^{\sqrt{2n}}\prod _{p\in {\mathbb{\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}⩽(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⩽\frac{\sqrt{2n}}{3}$, bo $n⩾18$, więc

$4^{\frac{n}{3}}⩽(2n{)}^{\frac{4}{3}\sqrt{2n}}$

Logarytmując obie strony nierówności otrzymujemy

$\sqrt{2n}\le 4\cdot \lg (2n)$

Podstawmy $n=2^{2t-1}$. Wtedy $\frac{2^t}{t}\le 4$, a więc $t<6$, co w stoi sprzeczności z $n>2048$, gdyż

$n=\frac{2^{2t}}{2}<\frac{2^{2\cdot 6}}{2}=2048$

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,\dots ,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{\mathbb{P}}}_n$ będzie zbiorem liczb pierwszych niewiększych od $n$ oraz $\pi (n)=\left|{\mathbb{\mathbb{P}}}_n\right|$.

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=10000$ mniej więcej co $9$-ta liczba jest pierwsza, tymczasem w pobliżu $n=1000000000$ 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

$\prod _{p\in {\mathbb{\mathbb{P}}}_n}<4^n$

Ponieważ w oczywisty sposób $\pi (n)!\le \prod _{p\in {\mathbb{\mathbb{P}}}_n}$, to ze wzoru Stirlinga mamy:

${\left(\frac{\pi (n)}{e}\right)}^{\pi (n)}<(\pi (n))!<\prod _{p\in {\mathbb{\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)$.

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\le n$ ma nietrywialny dzielnik (różny od 1 i niej samej), to $m$ ma nietrywialny dzielnik pierwszy, niewiększy od $\sqrt{n}$.