Podstawowe twierdzenie arytmetyki

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

Treść twierdzenia

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

Jednoznaczność rozkładu oznacza, że jeśli liczba n jest przedstawiona jako iloczyn pewnych liczb pierwszych na kilka sposobów, to wszystkie te iloczyny zawierają te same czynniki i w tej samej liczbie, 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=5\cdot 2\cdot 3\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_{1}m_{2}.$ Wówczas jednak $1<n<m_{1},m_{2}.$ Na mocy założenia indukcyjnego każde z $m_{1},m_{2}$ jest skończonym iloczynem liczb 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},\dots ,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},\dots ,p_{k}=q_{l},$

przy czym $k=l.$ Na koniec wystarczy udowodnić, że dla każdego $n\leqslant 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\leqslant 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.

Linki zewnętrzne

• Timothy Gowers, Proving the fundamental theorem of arithmetic, gowers.wordpress.com, 18 listopada 2011 (Dowód zasadniczego twierdzenia arytmetyki), [dostęp 2021-02-24].