Podstawowe twierdzenie arytmetyki

Podstawowe twierdzenie arytmetyki – ważne twierdzenie teorii liczb o rozkładzie liczb naturalnych na czynniki pierwsze.

Treść twierdzenia

Każdą liczbę naturalną większą od 1 można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.

W szczególności, liczbę pierwszą można przedstawić jako iloczyn zawierający jeden czynnik.

Jednoznaczność rozkładu oznacza, że jeśli liczba n jest przedstawiona jako iloczyn pewnych liczb pierwszych na dwa sposoby, to oba iloczyny zawierają te same czynniki i w tej samej ilości, a różnią się jedynie ich kolejnością. Na przykład:

$180 = 3\cdot 2\cdot 3\cdot 2\cdot 5 = 2\cdot 3\cdot 5\cdot 3\cdot 2.$

Zwykle czynniki pierwsze danej liczby grupuje się od najmniejszych do największych, czyli:

$180 = 2\cdot 2\cdot 3\cdot 3\cdot 5 = 2^2\cdot 3^2\cdot 5$.

Dowód

Lemat I

Każda liczba naturalna większa od 1 posiada przynajmniej jeden dzielnik będący liczbą pierwszą.

Niech $n>1\,$. Ponieważ $n|n\,$ więc zbiór dzielników liczby $n\,$ większych od 1 jest niepusty. Niech $d\,$ będzie najmniejszym z nich. Gdyby $d\,$ nie było pierwsze, to istniałby jego dzielnik $k<d\,$ i byłby to zarazem dzielnik $n\,$. Przeczy to jednak określeniu $d\,$ jako najmniejszego dzielnika $n\,$. Ostatecznie $d\,$ jest pierwszym dzielnikiem $n\,$.

Lemat II

Każda liczba naturalna większa od 1 daje się przedstawić jako skończony iloczyn samych liczb pierwszych.

Indukcyjnie. Twierdzenie jest prawdziwe dla $n=2\,$.

Niech $m\,$ będzie dowolną liczbą naturalną >2 i niech twierdzenie będzie prawdziwe dla wszystkich $1<n<m\,$.

Jeśli $m\,$ jest pierwsze to twierdzenie zachodzi.

Jeśli $m\,$ jest złożone, to $m=m_1m_2\,$. Wówczas jednak $1<m_1,m_2<m\,$. Na mocy założenia indukcyjnego każde z $m_1, m_2\,$ jest skończonym iloczynem liczby pierwszych, stąd także $m\,$ jest takim iloczynem.

Lemat III

Jeżeli $a$ jest liczbą całkowitą, a $p$ liczbą pierwszą, to albo $a$ jest podzielne przez $p$, albo $a$ i $p$ są względnie pierwsze

$p$, jako liczba pierwsza, posiada tylko dwa dzielniki naturalne - $1$ i $p$. Zatem albo $\operatorname{NWD}(a, p) = 1$, albo $\operatorname{NWD}(a, p) = p$. W pierwszym wypadku $a$ i $p$ są względnie pierwsze, w drugim $p$ dzieli $a$.

Z tego lematu bezpośrednio wynika inne twierdzenie:

Jeżeli $p$ i $q$ są liczbami pierwszymi, to albo $\operatorname{NWD}(p, q) = 1$, albo $p=q$.

Dowód twierdzenia

Niech $n$ będzie liczbą naturalną większą od jednego. Na mocy lematu II da się rozłożyć na czynniki pierwsze. Niech

$n=p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} ,\quad n=q_1^{\beta_1} q_2^{\beta_2} q_3^{\beta_3} \cdots q_l^{\beta_l}$

Gdyby żadna z liczb $q_1, q_2, \ldots, q_l$ nie była równa $p_1$, to, ze względu na lemat III, wszystkie byłyby pierwsze względem $p_1$. Liczba $n$ byłaby zatem iloczynem samych liczb pierwszych względem $p_1$, więc sama byłaby pierwsza względem $p_1$, co jest niemożliwe, gdyż $p_1$ dzieli $n$ w związku z pierwszym z wypisanych rozwinięć. Wynika z tego fakt, iż wśród liczb $q$ znajduje się liczba $p_1$. Analogicznie można udowodnić, że wśród liczb $q$ znajduje się każda liczba ze zbioru $p$ i na odwrót.

Zbiory liczb $p$ i $q$ są zatem identyczne i jeżeli uporządkujemy je na przykład rosnąco, to będziemy mieli

$p_1=q_1, p_2=q_2, \ldots, p_k=q_l$

przy czym $k=l$. Na koniec wystarczy udowodnić, że dla każdego $n \le k$, $\alpha_n = \beta_n$. Otóż niech na przykład $\alpha_1 < \beta_1$. Wtedy $\beta_1 = \alpha_1 + \delta_1$. Zatem:

$p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} = p_1^{\beta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_l^{\beta_l}$

$p_1^{\beta_1} = p_1^{\alpha_1 + \delta_1} = p_1^{\alpha_1} p_1^{\delta_1}$

$p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} = p_1^{\alpha_1} p_1^{\delta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_l^{\beta_l}$

Dzieląc obydwie strony równości przez $p_1^{\alpha_1}$, otrzymujemy:

$p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_k^{\alpha_k} = p_1^{\delta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_l^{\beta_l}$

Prawa strona zawiera czynnik $p_1$, więc jest przez niego podzielna, lewa strona z kolei, jako iloczyn liczb pierwszych różnych od $p_1$, jest względnie pierwsza z $p_1$, co jest sprzecznością. Niemożliwe jest zatem by $\alpha_1 < \beta_1$. W ten sam sposób można udowodnić, że niemożliwe jest również $\beta_1 < \alpha_1$, jak również $\alpha_n < \beta_n$ dla każdego $n \le k$.

Ciągi $p$ i $q$ są równe, jak również ciągi $\alpha$ i $\beta$, co znaczy, że obydwa rozkłady są identyczne, co było do pokazania.

Uogólnienia

Zbiór liczb całkowitych jest najmniejszym pierścieniem liczbowym zawierającym liczby naturalne. Podstawowe twierdzenie arytmetyki wyraża fakt, że pierścień ten jest pierścieniem z jednoznacznością rozkładu (pierścieniem Gaussa). Własność tę posiadają także pierścienie wielomianów – tam rolę elementów pierwszych odgrywają wielomiany nierozkładalne. Dla pierścienia $\mathbb C[x]$ jedynymi takimi wielomianami są wielomiany stopnia pierwszego – jest to treść zasadniczego twierdzenia algebry.

Twierdzenie o jednoznaczności rozkładu jest podstawą wielu metod matematyki i kryptografii.