Każda liczba \( b>1 \) ma przynajmniej dwa dodatnie dzielniki: \( 1 \) oraz \( b \).
Liczba pierwsza to liczba naturalna \( p \) posiadająca dokładnie dwa różne dzielniki. W szczególności \( p>1 \).
Przykład
Oto lista wszystkich liczb pierwszych mniejszych od \( 100 \):
\( 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97. \)
Liczba złożona to liczba naturalna \( a \), która nie jest pierwsza, a więc ma jakiś dodatni dzielnik różny od \( 1 \) i \( a \).
Liczby względnie pierwsze to takie liczby \( a \) i \( b \), dla których \( {\sf NWD}\ (a,b)=1 \), co zapisujemy inaczej jako \( a\perp b \).
Przykład
Wspomniane Elementy Euklidesa zawierają słynny lemat:
Lemat 10.2 [Lemat Euklidesa]
Jeśli \( n|ab \) i \( n\perp a \), to \( n|b \).
Dowód
Ponieważ \( {\sf NWD}\ (a,n)=1 \), to istnieją \( x,y \) takie, że \( xa+yn=1 \). Mnożąc obie strony równości przez \( b \) otrzymujemy:
\( xab+ynb=b. \)
Z założenia wiemy, iż \( n \) dzieli lewą stronę powyższej równości. Musi zatem dzielić też prawą.
Obserwacja 10.3 [Rozkład na iloczyn liczb pierwszych]
Każdą liczbę \( n>1 \) można przedstawić jako iloczyn liczb pierwszych.
Dowód
Intuicyjnie, wystarczy rozkładać liczby złożone w iloczynie, aż wszystkie będą liczbami pierwszymi, na przykład
\( 168=28\cdot6=(4\cdot7)\cdot(2\cdot3)=(2\cdot2)\cdot7\cdot2\cdot3. \)
Dla formalnego dowodu załóżmy niewprost, iż istnieje liczba naturalna większa od \( 1 \), nierozkładalna na iloczyn liczb pierwszych. Korzystając z Zasady Minimum, weźmy najmniejszą taką liczbę \( n \). Musi to być liczba złożona, gdyż dowolna liczba pierwsza jest jednoelementowym iloczynem liczb pierwszych. A zatem \( n \) jest złożona i istnieją \( a,b>1 \) takie, że \( n=ab \). Ale wtedy \( a \) oraz \( b \) są mniejsze od \( n \), więc z minimalności \( n \), rozkładają się na iloczyn liczb pierwszych. Ale wtedy także \( n=ab \) byłoby iloczynem liczb pierwszych, co przeczy temu, że \( n \) jest nierozkładalna i kończy dowód.
Nietrywialnym faktem jest, że każda liczba \( n>1 \) jest jednoznacznie rozkładalna na iloczyn liczb pierwszych (z dokładnością do kolejności liczb w iloczynie). Fakt ten powszechnie znany jest jako Fundamentalne Twierdzenie Arytmetyki. Dowód tego twierdzenia w dużej części był już w Elementach Euklidesa, jednak pierwszy, pełny i poprawny dowód przedstawił Carl Friedrich Gauss.
Twierdzenie 10.4 [Fundamentalne Twierdzenie Arytmetyki]
Każda liczba naturalna \( n>1 \) ma jednoznaczny (z dokładnością do kolejności liczb w iloczynie) rozkład na iloczyn liczb pierwszych.
Dowód
Podamy dwa dowody tego twierdzenia.
Najpierw przedstawimy dowód pochodzący od Euklidesa. Niech \( n>1 \) będzie najmniejszą liczbą naturalną posiadającą dwa różne rozkłady na liczby pierwsze: \( p_1\ldots p_k=n=q_1\ldots q_m \), gdzie \( p_1\leq\ldots\leq p_k \) oraz \( q_1\leq\ldots\leq q_m \). Żadna z liczb \( p_i \) nie może pojawić wśród \( q_1,\ldots,q_m \) (i na odwrót), gdyż wydzielając obie strony przez \( p_i \), otrzymalibyśmy mniejszą liczbę z dwoma różnymi rozkładami. Liczba pierwsza \( p_1 \) dzieli pierwszy iloczyn, a więc też dzieli i drugi:
\( p_1|q_1\ldots q_m. \)
Zauważmy, że
\( p_1\perp q_1, \)
gdyż są to dwie, różne liczby pierwsze. Na mocy Lematu Euklidesa otrzymujemy, iż \( p_1|q_2\ldots q_m \). Kolejno możemy wyeliminować pozostałe liczby \( q_i \) z prawego iloczynu dochodząc do \( p_1|1 \), oczywistej sprzeczności.
A oto alternatywny dowód. Niech \( n \) będzie najmniejszą liczbą naturalną większą od \( 1 \) posiadającą dwa różne rozkłady na liczby pierwsze: \( p_1\ldots p_k=n=q_1\ldots q_m \), gdzie \( p_1\leq\ldots\leq p_k \) oraz \( q_1\leq\ldots\leq q_m \). Tak, jak poprzednio dostajemy, że żadna liczba pierwsza nie może być jednocześnie w obu rozkładach. Bez straty ogólności niech \( p_1 < q_1 \). Wtedy istnieje \( d,r\in\mathbb{Z} \) takie, że
\( q_1/p_1=d+r/p_1, \)
gdzie \( 0 < r < p_1 < q_1 \) (\( r \) nie może być równe \( 0 \), gdyż oznaczałoby to iż \( p_1|q_1 \)). Wymnażając obie strony równości przez \( q_2\ldots q_m \) otrzymujemy
\( p_2\ldots p_k=dq_2\ldots q_m+rq_2\ldots q_m/p_1. \)
Drugi składnik w prawej stronie tej równości musi być zatem liczbą naturalną. Oznaczając ją przez \( x \) mamy więc
\( xp_1=rq_2\ldots q_m. \)
Wartość obu stron powyższej równości jest mniejsza od \( n \), gdyż \( r < q_1 \). Ponieważ \( r < p_1 \), to po rozłożeniu liczby \( x \) na czynniki pierwsze dostaniemy dwa różne rozkłady liczby mniejszej od \( n \), co przeczy założeniu o minimalności \( n \).
Fundamentalne Twierdzenie Arytmetyki eksponuje znaczenie liczb pierwszych. Okazuje się, że są to podstawowe bloki, z których można zbudować w unikalny sposób dowolną liczbę naturalną większą od \( 1 \).
Przykład
\( 1925=5^2\cdot7\cdot11 \), \( 2006=2\cdot17\cdot59 \), \( 108=2^2\cdot3^3 \), \( 2048=2^{11} \).
Obecnie nie jest znany żaden efektywny algorytm faktoryzujący liczby naturalne, tzn. znajdujący rozkład na iloczyn liczb pierwszych. Oczekiwana trudność tego problemu jest sercem wielu współczesnych systemów kryptograficznych (np. RSA). Nie wszystkie liczby są równie trudne w rozkładzie. Póki co, (w połowie 2006 roku) najtrudniejsze wydają się liczby, które są iloczynami dwu liczb pierwszych podobnej długości.
Przykład
Aby choć trochę zrozumieć trudność problemu faktoryzacji proponujemy znaleźć nietrywialny dzielnik liczby złożonej \( 10721 \). Na stronie WWW firmy RSA podane są znacznie większe liczby, za rozkład których RSA skłonna jest płacić nawet 200 tys. USD.
Znajomość rozkładu liczby na czynniki pierwsze pozwala określić, w sposób systematyczny, wszystkie jej dzielniki.
Obserwacja 10.5
Jeśli \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) jest rozkładem liczby \( n \) na iloczyn liczb pierwszych, to każdy jej dzielnik \( d|n \) jest postaci \( d=p_{1}^{\beta_{1}}\ldots p_{k}^{\beta_{k}} \), dla pewnych \( 0\leq\beta_i\leq\alpha_i \).
Dowód
Załóżmy, dla dowodu niewprost, że w rozkładzie liczby \( d \) występuje liczba pierwsza, powiedzmy \( p \), która nie występuje w rozkładzie \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \). Oczywiście \( p|n \), bo \( d|n \). Ponieważ \( p \) i \( p_1 \) są dwiema różnymi liczbami pierwszymi, to na mocy Lematu Euklidesa otrzymujemy \( p|p_2^{\alpha_2}\ldots p_k^{\alpha_k} \). W podobny sposób możemy wyeliminować kolejno liczby \( p_2,\ldots,p_k \) dochodząc do sprzeczności, że \( p|1 \). A więc rozkład liczby \( d \) zawiera wyłącznie liczby pierwsze z rozkładu liczby\( n \), czyli \( d=p_1^{\beta_1}\ldots p_k^{\beta_k} \), przy czym oczywiście wszystkie \( \beta_i \) są nieujemne, ale niektóre mogą być zerowe. Pozostaje pokazać, że \( \beta_i\leq\alpha_i \). Załóżmy, że \( \beta_{i}>\alpha_{i} \) dla pewnego \( i \). Wtedy
\( \frac{d}{p_i^{\alpha_{i}}} \mbox{ \ dzieli \ } \frac{n}{p_i^{\alpha_{i}}}, \)
przy czym liczba \( \frac{d}{p_i^{\alpha_{i}}} \) ma w swoim rozkładzie czynnik \( p_{i} \), a liczba \( \frac{n}{p_i^{\alpha_{i}}} \) nie ma. To jednak stoi w sprzeczności z ustanowionym wcześniej faktem, że wszystkie czynniki rozkładu każdego dzielnika jakiejkolwiek liczby naturalnej występują w rozkładzie tego dzielnika.
Ponieważ ciągów liczb naturalnych \( (\beta_1,\ldots,\beta_k) \) spełniających \( 0\leq\beta_i\leq\alpha_i \) jest dokładnie \( (\alpha_1+1)\cdot(\alpha_2+1)\cdot\ldots\cdot(\alpha_k+1) \) z Obserwacji 10.5 dostajemy natychmiast:
Wniosek 10.6
Jeśli \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) jest rozkładem liczby \( n \) na iloczyn liczb pierwszych, to liczba \( n \) ma dokładnie \( (\alpha_1+1)\cdot(\alpha_2+1)\cdot\ldots\cdot(\alpha_k+1) \) dodatnich dzielników.
Przykład
Innym natychmiastowym wnioskiem z Obserwacji 10.5 jest:
Wniosek 10.7
Dla \( a,b,c\in\mathbb{N} \) jeśli \( a|c \), \( b|c \) i \( a\perp b \), to \( ab|c \).
Mając dany rozkład liczb \( a \) i \( b \) możemy błyskawicznie policzyć \( {\sf NWD}\ (a,b) \).
Obserwacja 10.8
Jeśli \( a,b>0 \), \( a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) i \( b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k} \), gdzie \( \alpha_i, \beta_i \geq 0 \), to
\( {\sf NWD}\ (a,b)=p_1^{\min(\alpha_1,\beta_1)}\cdot \ldots\cdot p_k^{\min(\alpha_k,\beta_k)}. \)
Dowód
Każdy wspólny dzielnik \( d|a,b \) jest postaci \( d=p_1^{\gamma_1}p_2^{\gamma_2}\ldots p_k^{\gamma_k} \), przy czym \( \gamma_i\leq\alpha_i \) oraz \( \gamma_i\leq\beta_i \). Oczywiście wśród liczb tej postaci, liczba \( p_1^{\min(\alpha_1,\beta_1)}\cdot \ldots\cdot p_k^{\min(\alpha_k,\beta_k)} \) jest największa.
Oczywiście mając rozkłady liczb \( a,b \) na czynniki pierwsze łatwo jest już policzyć \( {\sf NWD}\ (a,b) \). Jak jednak odnotowaliśmy uzyskanie takich rozkładów nie jest łatwe. Dzięki algorytmowi Euklidesa potrafimy jednak (efektywnie) znaleźć NWD dwóch liczb bez znajomości ich rozkładu.
Ważnym dualnym pojęciem do NWD jest pojęcie najmniejszej wspólnej wielokrotności dwu liczb.
Najmniejsza wspólna wielokrotność dwu liczb \( a,b>0 \) (oznaczana przez \( {\sf NWW}\ (a,b) \)) to najmniejsza liczba dodatnia \( w \) taka, że \( a|w \) i \( b|w \).
Znając rozkłady dwu liczb możemy, analogicznie do NWD , wyznaczyć ich NWW.
Obserwacja 10.9
Jeśli \( a,b>0 \), \( a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) i \( b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k} \), gdzie \( \alpha_i, \beta_i \geq 0 \), to
\( {\sf NWW}\ (a,b)=p_1^{\max(\alpha_1,\beta_1)}\cdot \ldots\cdot p_k^{\max(\alpha_k,\beta_k)}. \)
Na podstawie ostatnich dwu obserwacji dostajemy natychmiast:
Wniosek 10.10
\( {\sf NWD} \ (a,b) \cdot {\sf NWW} \ (a,b)=ab. \)
Wniosek ten można wykorzystać do szybkiego liczenia NWD dwu liczb bez znajomości ich rozkładów na czynniki pierwsze. Wyznaczywszy najpierw algorytmem Euklidesa wartość \( {\sf NWD}\ (a,b) \), wystarczy potem podzielić
\( {\sf NWW}\ (a,b)= \frac{a\cdot b}{ {\sf NWD}\ (a,b)}. \)