Podstawowe twierdzenie arytmetyki

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Treść twierdzenia[edytuj | edytuj kod]

Każdą liczbę naturalną większą od 1, nie bę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 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[1][edytuj | edytuj kod]

Lemat I[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Przypisy

  1. I. W: Wacław Sierpiński: Teoria liczb. Wyd. trzecie. Warszawa: Wydawnictwo Uniwersytetu Wrocławskiego, 1950, s. 8-10. (pol.)