Zasadnicze twierdzenie arytmetyki

Zasadnicze twierdzenie arytmetyki, podstawowe twierdzenie arytmetyki, 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ó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<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 $\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}}\ldots p_{k}^{\alpha _{k}},\quad n=q_{1}^{\beta _{1}}q_{2}^{\beta _{2}}q_{3}^{\beta _{3}}\ldots 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}}\ldots p_{k}^{\alpha _{k}}=p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}p_{3}^{\beta _{3}}\ldots 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}}\ldots p_{k}^{\alpha _{k}}=p_{1}^{\alpha _{1}}p_{1}^{\delta _{1}}p_{2}^{\beta _{2}}p_{3}^{\beta _{3}}\ldots 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}}\ldots p_{k}^{\alpha _{k}}=p_{1}^{\delta _{1}}p_{2}^{\beta _{2}}p_{3}^{\beta _{3}}\ldots 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

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.

Bibliografia

• Podzielność liczb i rozkład na czynniki pierwsze. W: Wacław Sierpiński: Teoria liczb. Wyd. trzecie. Warszawa – Wrocław: Wydawnictwo Uniwersytetu Wrocławskiego, 1950.

Linki zewnętrzne

• BartłomiejB. Bzdęga BartłomiejB., Jednoznaczność rozkładu w N – część 2, „Delta”, lipiec 2021, ISSN 0137-3005 [dostęp 2024-02-10] .
• Timothy Gowers, Proving the fundamental theorem of arithmetic, gowers.wordpress.com, 18 listopada 2011 (Dowód zasadniczego twierdzenia arytmetyki), [dostęp 2021-02-24].