Zasadnicze twierdzenie arytmetyki

Zasadnicze twierdzenie arytmetyki^[1][2], podstawowe twierdzenie arytmetyki^{[potrzebny przypis]}, fundamentalne twierdzenie arytmetyki^[3] – 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^[4] – 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:

${\displaystyle 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^[3]. Nazwa pojawiła się najpóźniej w 1915 roku, kiedy użył jej Eric Temple Bell^[5].

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

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

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

Indukcyjnie. Twierdzenie jest prawdziwe dla ${\displaystyle n=2.}$

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

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

Jeśli ${\displaystyle m}$ jest złożone, to ${\displaystyle m=m_{1}m_{2}.}$ Wówczas jednak ${\displaystyle 1<m_{1}<m}$ oraz ${\displaystyle 1<m_{2}<m}$. Na mocy założenia indukcyjnego każde z ${\displaystyle m_{1}}$ i ${\displaystyle m_{2}}$ jest skończonym iloczynem liczb pierwszych, stąd także ${\displaystyle m}$ jest takim iloczynem.

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

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

Z tego lematu bezpośrednio wynika inne twierdzenie:

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

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

${\displaystyle 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 ${\displaystyle q_{1},q_{2},\dots ,q_{l}}$ nie była równa ${\displaystyle p_{1},}$ to, ze względu na lemat III wszystkie byłyby pierwsze względem ${\displaystyle p_{1}.}$ Liczba ${\displaystyle n}$ byłaby zatem iloczynem samych liczb pierwszych względem ${\displaystyle p_{1},}$ więc sama byłaby pierwsza względem ${\displaystyle p_{1},}$ co jest niemożliwe, gdyż ${\displaystyle p_{1}}$ dzieli ${\displaystyle n}$ w związku z pierwszym z wypisanych rozwinięć. Wynika z tego fakt, iż wśród liczb ${\displaystyle q}$ znajduje się liczba ${\displaystyle p_{1}.}$ Analogicznie można udowodnić, że wśród liczb ${\displaystyle q}$ znajduje się każda liczba ze zbioru ${\displaystyle p}$ i na odwrót.

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

${\displaystyle p_{1}=q_{1},p_{2}=q_{2},\dots ,p_{k}=q_{l},}$

przy czym ${\displaystyle k=l.}$ Na koniec wystarczy udowodnić, że dla każdego ${\displaystyle n\leqslant k,}$ ${\displaystyle \alpha _{n}=\beta _{n}.}$ Otóż niech na przykład ${\displaystyle \alpha _{1}<\beta _{1}.}$ Wtedy ${\displaystyle \beta _{1}=\alpha _{1}+\delta _{1}.}$ Zatem:

${\displaystyle 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}},}$

${\displaystyle p_{1}^{\beta _{1}}=p_{1}^{\alpha _{1}+\delta _{1}}=p_{1}^{\alpha _{1}}p_{1}^{\delta _{1}},}$

${\displaystyle 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 ${\displaystyle p_{1}^{\alpha _{1}},}$ otrzymujemy:

${\displaystyle 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 ${\displaystyle p_{1},}$ więc jest przez niego podzielna, lewa strona z kolei, jako iloczyn liczb pierwszych różnych od ${\displaystyle p_{1},}$ jest względnie pierwsza z ${\displaystyle p_{1},}$ co jest sprzecznością. Niemożliwe jest zatem, by ${\displaystyle \alpha _{1}<\beta _{1}.}$ W ten sam sposób można udowodnić, że niemożliwe jest również ${\displaystyle \beta _{1}<\alpha _{1},}$ jak również ${\displaystyle \alpha _{n}<\beta _{n}}$ dla każdego ${\displaystyle n\leqslant k.}$

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

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

• 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.

• 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].