Fundamentalne twierdzenie arytmetyki — definicja i unikalna faktoryzacja liczb
Fundamentalne twierdzenie arytmetyki — definicja i unikalna faktoryzacja liczb. Poznaj zasady rozkładu na liczby pierwsze, dowód i zastosowania w faktoryzacji i kryptografii.
Fundamentalne twierdzenie arytmetyki (zwane również twierdzeniem o jedynej faktoryzacji) jest twierdzeniem teorii liczb. Twierdzenie to stwierdza, że każda liczba całkowita dodatnia większa od 1 może być zapisana jako iloczyn liczb pierwszych (zwykle przedstawiany z wykładnikami, np. 23·3·172). Twierdzenie to mówi również, że istnieje tylko jeden sposób zapisania tej liczby jako iloczynu liczb pierwszych, z zastrzeżeniem kolejności czynników. Oznacza to, że jeśli dwie osoby znalazły dwa różne zapisy tej samej liczby jako iloczyn liczb pierwszych, to po uporządkowaniu czynników oba zapisy będą identyczne.
Przykłady: 6936 = 23·3·172 oraz 1200 = 24·3·52.
Proces rozkładania liczby na czynniki pierwsze nazywamy faktoryzacją. Warto zaznaczyć, że liczba 1 jest wyłączona z twierdzenia — 1 nie jest ani liczbą pierwszą, ani złożoną, i w teorii pierścieni pełni rolę jednostki; gdyby włączyć 1 do faktoryzacji, to uniklano by jednoznaczności (można by dowolnie dołączać kolejne jedynki).
Zarys dowodu
Dowód twierdzenia dzieli się zwykle na dwie części:
- Istnienie: Pokazujemy, że każda liczba n>1 ma rozkład na czynniki pierwsze. Najprostszy sposób to silna indukcja: jeśli n jest pierwsza, mamy już rozkład. Jeśli n jest złożona, istnieje dzielnik d taki, że 1
- Jedyność: Aby pokazać, że rozkład jest jednoznaczny (oprócz kolejności czynników), korzystamy z tzw. lematów Euklidesa: jeśli liczba pierwsza p dzieli iloczyn ab, to p dzieli a lub p dzieli b. Dzięki temu, porównując dwa różne rozkłady tej samej liczby, można kolejno "usuwać" takie same czynniki pierwsze, aż dojdzie się do stwierdzenia, że rozkłady muszą zawierać te same czynniki (z takim samym wykładnikiem).
Znaczenie i zastosowania
Fundamentalne twierdzenie arytmetyki jest jednym z podstawowych rezultatów arytmetyki i leży u podstaw wielu dalszych pojęć w teorii liczb. Ma też praktyczne zastosowania — w szczególności w kryptografii. W systemach takich jak RSA bezpieczeństwo opiera się na fakcie, że rozkład dużych liczb na czynniki pierwsze jest w praktyce trudny do przeprowadzenia (brak znanych efektywnych algorytmów klasycznych dla bardzo dużych liczb), choć sam fakt istnienia i jednoznaczności rozkładu jest gwarantowany przez to twierdzenie.
Uogólnienia
W teorii algebraicznej istnieją uogólnienia tego pojęcia: nie wszystkie struktury pierścieniowe mają jednoznaczny rozkład na "pierwsze elementy". Pierścienie, w których każdy element ma rozkład jednoznaczny na czynniki (do jednostek i kolejności) nazywa się dziedzinami faktoryzacji jednoznacznej (UFD — unique factorization domains). Przykładem UFD jest pierścień liczb całkowitych Z, dla którego sformułowane jest tutaj twierdzenie.
Dowód
Pierwszą osobą, która udowodniła to twierdzenie był Euklides. Pierwszy szczegółowy i poprawny dowód znalazł się w Disquisitiones Arithmeticae Carla Friedricha Gaußa.
Niektórzy ludzie mogą myśleć, że to twierdzenie jest prawdziwe wszędzie. Jednakże, twierdzenie to nie jest prawdziwe w bardziej ogólnych systemach liczbowych, takich jak algebraiczne liczby całkowite. Po raz pierwszy wspomniał o tym Ernst Kummer w 1843 roku, w swojej pracy na temat ostatniego twierdzenia Fermata. Więcej informacji na ten temat: przeczytaj algebraiczną teorię liczb.
Dowód składa się z dwóch części: po pierwsze pokazujemy, że każdą liczbę można zapisać jako iloczyn liczb pierwszych; po drugie pokazujemy, że jeśli po raz drugi zapiszemy daną liczbę jako iloczyn liczb pierwszych, to obie listy liczb pierwszych muszą być takie same.
Pierwsza część dowodu
Pokazujemy, że jeśli nie każda liczba większa od 1 może być zapisana jako iloczyn liczb pierwszych, to kończymy w jakimś rodzaju niemożliwości. Stąd wniosek, że musi być prawdą, że każda liczba może być zapisana jako iloczyn liczb pierwszych.
Zobaczmy teraz, co się stanie, gdy ktoś powie, że zna liczbę całkowitą dodatnią większą od 1, której nie można zapisać jako iloczynu liczb pierwszych. W takim przypadku prosimy go, by wymienił wszystkie liczby większe od 1, których nie da się zapisać jako iloczynu liczb pierwszych. Jedna z tych liczb musi być najmniejsza: nazwijmy ją n. Oczywiście ta liczba n nie może być 1. Ponadto, nie może być liczbą pierwszą, ponieważ liczba pierwsza jest "produktem" jednej liczby pierwszej: samej siebie. Zatem musi to być iloczyn liczb. Tak więc -
n = ab
gdzie zarówno a jak i b są dodatnimi liczbami całkowitymi, które są oczywiście mniejsze od n. Ale: n było najmniejszą liczbą, która nie może być zapisana jako iloczyn liczb pierwszych. Zatem musi być możliwe zapisanie a i b jako iloczynów liczb pierwszych, ponieważ obie są mniejsze od n. Ale wtedy iloczyn
n = ab
może być również zapisane jako iloczyn liczb pierwszych. Jest to niemożliwe, ponieważ powiedzieliśmy, że n nie może być zapisane jako iloczyn liczb pierwszych.
Pokazaliśmy teraz niemożliwość, która istnieje, jeśli pierwsza część twierdzenia nie byłaby prawdziwa. W ten sposób udowodniliśmy pierwszą część twierdzenia.
Druga część dowodu
Teraz musimy udowodnić, że istnieje tylko jeden sposób, aby zapisać liczbę dodatnią większą od 1 jako iloczyn liczb pierwszych.
W tym celu posłużymy się następującym lematem: jeśli liczba pierwsza p dzieli iloczyn ab, to dzieli a lub dzieli b (lemat Euklidesa). Najpierw udowodnimy ten lemat. Załóżmy, że p nie dzieli a. Wtedy p i a są współwystępujące i mamy tożsamość Bezouta, która mówi, że muszą istnieć liczby całkowite x i y takie, że
px + ay = 1.
Mnożąc wszystko przez b otrzymujemy
pbx + aby = b,
Pamiętajmy, że ab może być podzielne przez p. Zatem teraz po lewej stronie mamy dwa wyrazy, które są podzielne przez p. Zatem wyraz po prawej stronie jest również podzielny przez p. Udowodniliśmy, że jeśli p nie dzieli a, to musi dzielić b. To dowodzi lematu.
Teraz udowodnimy, że liczbę całkowitą większą od 1 możemy zapisać tylko w jeden sposób jako iloczyn liczb pierwszych. Weźmy dwa iloczyny liczb pierwszych A i B, które mają ten sam wynik. Wiemy więc, że A = B. Weźmy dowolną liczbę pierwszą p z pierwszego iloczynu A. Dzieli ona A, więc dzieli też B. Korzystając kilkakrotnie z lematu, który właśnie udowodniliśmy, widzimy, że p musi wtedy dzielić co najmniej jeden czynnik b z B. Ale wszystkie te czynniki są same w sobie liczbami pierwszymi, więc również b jest pierwsze. Wiemy, że p jest również pierwsze, więc p musi być równe b. Teraz więc dzielimy A przez p i dzielimy B przez p. Otrzymujemy wynik taki jak A* = B*. Ponownie możemy wziąć liczbę pierwszą p z pierwszego produktu A* i dowiedzieć się, że jest ona równa pewnej liczbie w produkcie B*. Kontynuując w ten sposób, na końcu widzimy, że czynniki pierwsze obu iloczynów muszą być dokładnie takie same. To dowodzi, że liczbę całkowitą dodatnią możemy zapisać jako iloczyn liczb pierwszych tylko w jeden jedyny sposób.
Pytania i odpowiedzi
P: Co to jest podstawowe twierdzenie arytmetyki?
O: Fundamentalne twierdzenie arytmetyki to twierdzenie teorii liczb, które mówi, że każdą liczbę całkowitą dodatnią większą od 1 można zapisać jako iloczyn liczb pierwszych, a liczba ta może być zapisana tylko w jeden sposób.
P: Jak można wykorzystać to twierdzenie?
O: To twierdzenie można wykorzystać w kryptografii.
P: Co się stanie, jeżeli dwie osoby znajdą dwa różne sposoby zapisania tej samej liczby?
O: Jeżeli dwie osoby znajdą dwa różne sposoby zapisania tej samej liczby, to jedyną rzeczą, która może być różna, jest kolejność zapisywania pierwiastków.
P: Co to jest faktoryzacja?
O: Faktoryzacja to znalezienie wszystkich liczb pierwszych, które składają się na daną liczbę.
P: Czy 6936 jest przykładem liczby pierwszej?
O: Nie, 6936 nie jest liczbą pierwszą; można ją zapisać jako 23 - 3 - 172.
Nie, 6936 nie jest liczbą pierwszą; można ją zapisać jako 23 - 3 - 172.
Przeszukaj encyklopedię