Zasadnicze twierdzenie arytmetyki

Zasadnicze twierdzenie arytmetykiSzablon:Odn, podstawowe twierdzenie arytmetykiSzablon:Fakt, fundamentalne twierdzenie arytmetyki – twierdzenie teorii liczb o rozkładzie liczb naturalnych na czynniki pierwsze. Mówi ono, że każda liczba złożona to iloczyn liczb pierwszych i rozkład ten jest jednoznaczny – zapisy mogą się różnić jedynie kolejnością czynników. Krótkie sformułowanie w języku algebry abstrakcyjnej mówi, że pierścień liczb całkowitych ma jednoznaczność rozkładu – jest pierścieniem Gaussa.

Na przykład:

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

czynniki pierwsze pogrupowano tu rosnąco – od najmniejszych do największych.

Pełne sformułowanie i ścisły dowód tego twierdzenia podał najpóźniej Carl Friedrich Gauss, choć fakty wykorzystywane w dowodzie znał wcześniej Euklides. Nazwa pojawiła się najpóźniej w 1915 roku, kiedy użył jej Eric Temple Bell.

DowódSzablon:Odn

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<m_1<m$ oraz $1<m_2<m$. Na mocy założenia indukcyjnego każde z $m_1$ i $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 $\mathrm{NWD}(a,p)=1,$ albo $\mathrm{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

$\mathrm{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}\dots p_k^{{\alpha }_k},n=q_1^{{\beta }_1}{q}_2^{{\beta }_2}{q}_3^{{\beta }_3}\dots 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⩽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}\dots p_k^{{\alpha }_k}=p_1^{{\beta }_1}{p}_2^{{\beta }_2}{p}_3^{{\beta }_3}\dots 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}\dots p_k^{{\alpha }_k}=p_1^{{\alpha }_1}{p}_1^{{\delta }_1}{p}_2^{{\beta }_2}{p}_3^{{\beta }_3}\dots 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}\dots p_k^{{\alpha }_k}=p_1^{{\delta }_1}{p}_2^{{\beta }_2}{p}_3^{{\beta }_3}\dots 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⩽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

Własność tę posiadają także pierścienie wielomianów – tam rolę elementów pierwszych odgrywają wielomiany nierozkładalne. Dla pierścienia $ℂ[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.

Bibliografia

• Szablon:Cytuj książkę

Linki zewnętrzne

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