Matematyka dyskretna 1/Wykład 10: Teoria liczb

{thm}{Twierdzenie} {obs}[thm]{Obserwacja} {con}[thm]{Wniosek} {lemat}{Lemat}

{article}

{../makraP}

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: Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \mbox{ {\sf mod} } b } .

Przykład

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 47 \mbox{ {\sf mod} } 9 =2} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1823 \mbox{ {\sf mod} } 2 =1} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 32 \mbox{ {\sf mod} } 43 =32} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 111 \mbox{ {\sf mod} } 13 =7} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle -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. Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \mbox{ {\sf mod} } b =0} .

Obserwacja

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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, Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1\leqslant\mbox{\sf NWD}(a,b)\leq \min(\left\verta\right\vert,\left\vertb\right\vert)} .

Przykład

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(30,75)=15} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(10,3)=1} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\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.

Algorytm Euklidesa.

1. Wczytaj liczby $a,b>0$.

1. Oblicz $r$ jako resztę z dzielenia $a$ przez $b$.

1. Zastąp $a$ przez $b$, zaś $b$ przez $r$.

1. Jeżeli $b=0$ to zwróć $a$ w przeciwnym wypadku przejdź do (2).

Przykład

Przebieg obliczenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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$.

Applet: 1. Dwa pola na wprowadzenie liczb. Przycisk zatwierdzający, po naciśnięciu którego pojawiają się obliczenia Algorytmu Euklidesa, tak jak w przykładzie powyżej. Błąd wejścia sygnalizowany jest gdy wprowadzone liczby nie są dodatnie i całkowite. Najlepiej aby pola do wprowadzania liczb miały ograniczona wielkość (np. 5-8 cyfr).

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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,\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD }} .

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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\dots ,r_n,r_{n+1}$ będą kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym $r_{n+1}=0$. Wtedy wiemy, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_n=\mbox{\sf NWD}(a,b)} oraz

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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,\dots ,q_{n-1}$. Mamy zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_{n-2}-q_{n-2}\cdot r_{n-1}=\mbox{\sf NWD}(a,b)} . Załóżmy indukcyjnie, dla $0<i\le n-2$, że istnieją $x,y\in \mathbb{\mathbb{Z}}$ takie, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,b)} ($a\ge b$) algorytmem Euklidesa wystarcza $O({\lg }^{3}a)$ operacji bitowych.

Aby policzyć współczynniki $x$, $y$ takie, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle ax+by=\mbox{\sf NWD}(a,b)} , zgodnie z przedstawionym dowodem, należy przedstawić Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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$.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(1547,560)=7} . Aby wyrazić $7$ jako kombinację danych wejściowych liczymy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}

Applet: 2. Roszerzona wersja appletu 1.. Obok standarodwych obliczeń Algorytmu Eulkidesa powinno się pojawić obliczenie współczynników rozszerzonego algorytmu, jak w przykładzie powyżej.

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,b)=1} , co zapisujemy inaczej jako $a\perp b$.

Przykład

• $10\perp 3$ bo Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(10,3)=1} ,

• $12\perp ̸3$ bo Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(12,3)=3} ,

• $7\perp 15$ bo Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(7,15)=1} .

Wspomniane Elementy Euklidesa zawierają słynny lemat:

Lemat Lemat Euklidesa

Jeśli $n|ab$ i $n\perp a$, to $n|b$.

Dowód

Ponieważ Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ą.

Obserwacja 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 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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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,\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 Uzupelnic dzielniki| dostajemy natychmiast:

Wniosek

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 Uzupelnic dzielniki| jest:

Wniosek

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ć Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,b)} .

Obserwacja

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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}\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ć Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ść Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,b)} , wystarczy potem podzielić

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

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 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$):

{

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

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)\le m\cdot \ln 4+(m+1)\cdot \ln 4=n\cdot \ln 4.$

Twierdzenie 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 Uzupelnic vartheta| 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 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

$\pi (n)=O(n/\ln n)$.

Dowód

Lemat Uzupelnic vartheta| 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.

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

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

Applet: 3. Coś wzorowanego na animacji z http://pl.wikipedia.org/wiki/SitoEratostenesa Liczb w wierszu może być nawet $20$ (ogółem do $400$, ale bez $1$!). Jedno pole do wprowadzenia liczby ze zbioru $\left\{10,\dots ,400\right\}$ (jeśli inna wprowadzona to błąd wejścia). Po zatwierdzeniu wejścia (jakimś przyciskiem) odpalona jest procedura sita. Wykreślane liczby mogą byc przekreślane jakimś krzyżykiem, te które są uznane za pierwsze sa listowane z boku (jak na www).