Podstawowe twierdzenie arytmetyki

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

Treść twierdzeniaEdytuj

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

Lemat IEdytuj

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 IIEdytuj

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 IIIEdytuj

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 twierdzeniaEdytuj

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ólnieniaEdytuj

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.

PrzypisyEdytuj

  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.