Podstawowe twierdzenie arytmetyki

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Podstawowe twierdzenie arytmetyki – 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[1].

Jednoznaczność rozkładu oznacza, że jeśli liczba n jest przedstawiona jako iloczyn pewnych liczb pierwszych na kilka sposobów, to wszystkie te iloczyny zawierają te same czynniki i w tej samej liczbie, 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[2][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 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 | 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

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 liczb pierwszych, stąd także jest takim iloczynem.

Lemat III[edytuj | edytuj kod]

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

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

  1. Eric W. Weisstein, Fundamental Theorem of Arithmetic, mathworld.wolfram.com [dostęp 2017-10-29] (ang.).
  2. 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, s. 8–10.