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:
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].
Dowód[6]
Lemat I
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
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
oraz
. Na mocy założenia indukcyjnego każde z
i
jest skończonym iloczynem liczb pierwszych, stąd także
jest takim iloczynem.
Lemat III
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
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
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
Bibliografia
- 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.
Linki zewnętrzne
- Bartłomiej Bzdęga , Jednoznaczność rozkładu w N – część 2, [w:] pismo „Delta”, deltami.edu.pl, lipiec 2021, ISSN 0137-3005 [dostęp 2024-02-10] (pol.).
Timothy Gowers, Proving the fundamental theorem of arithmetic, gowers.wordpress.com, 18 listopada 2011 (Dowód zasadniczego twierdzenia arytmetyki), [dostęp 2021-02-24].