Podstawowe twierdzenie arytmetyki

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Treść twierdzenia[edytuj]

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:

Zwykle czynniki pierwsze danej liczby grupuje się od najmniejszych do największych, czyli:

.

Dowód[1][edytuj]

Lemat I[edytuj]

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

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

Lemat II[edytuj]

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

Indukcyjnie. Twierdzenie jest prawdziwe dla .

Niech będzie dowolną liczbą naturalną >2 i niech twierdzenie będzie prawdziwe dla wszystkich .

Jeśli jest pierwsze to twierdzenie zachodzi.

Jeśli jest złożone, to . Wówczas jednak . Na mocy założenia indukcyjnego każde z jest skończonym iloczynem liczby pierwszych, stąd także jest takim iloczynem.

Lemat III[edytuj]

Jeżeli jest liczbą całkowitą, a liczbą pierwszą, to albo jest podzielne przez , albo i są względnie pierwsze

, jako liczba pierwsza, posiada tylko dwa dzielniki naturalne - i . Zatem albo , albo . W pierwszym wypadku i są względnie pierwsze, w drugim dzieli .

Z tego lematu bezpośrednio wynika inne twierdzenie:

Jeżeli i są liczbami pierwszymi, to albo , albo .

Dowód twierdzenia[edytuj]

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

Gdyby żadna z liczb nie była równa , to, ze względu na lemat III, wszystkie byłyby pierwsze względem . Liczba byłaby zatem iloczynem samych liczb pierwszych względem , więc sama byłaby pierwsza względem , co jest niemożliwe, gdyż dzieli w związku z pierwszym z wypisanych rozwinięć. Wynika z tego fakt, iż wśród liczb znajduje się liczba . Analogicznie można udowodnić, że wśród liczb znajduje się każda liczba ze zbioru i na odwrót.

Zbiory liczb i są zatem identyczne i jeżeli uporządkujemy je na przykład rosnąco, to będziemy mieli

przy czym . Na koniec wystarczy udowodnić, że dla każdego , . Otóż niech na przykład . Wtedy . Zatem:

Dzieląc obydwie strony równości przez , otrzymujemy:

Prawa strona zawiera czynnik , więc jest przez niego podzielna, lewa strona z kolei, jako iloczyn liczb pierwszych różnych od , jest względnie pierwsza z , co jest sprzecznością. Niemożliwe jest zatem by . W ten sam sposób można udowodnić, że niemożliwe jest również , jak również dla każdego .

Ciągi i są równe, jak również ciągi i , co znaczy, że obydwa rozkłady są identyczne, co było do pokazania.

Uogólnienia[edytuj]

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