Podstawowe twierdzenie arytmetyki

Q: Dlaczego jedynka nie jest liczbą pierwszą?

Bo zniszczyłaby jednoznaczność rozkładu - każdą liczbę można by mnożyć przez dowolną potęgę jedynki. Definicja jest dobrana tak, by twierdzenie pozostało prawdziwe.

Q: Czy zero i liczby ujemne mają rozkład?

Twierdzenie dotyczy liczb naturalnych większych od 1. Dla ujemnych stosuje się je do wartości bezwzględnej, dopisując znak; zero rozkładu nie ma, bo dzieli się przez wszystko.

Q: Czy jednoznaczność rozkładu to nie jest oczywiste?

Nie - i najlepiej pokazuje to przykład pierścienia liczb a + b√-5, w którym 6 ma dwa różne rozkłady. Jednoznaczność jest własnością liczb całkowitych, a nie prawem natury.

Q: Jak szybko można rozłożyć dużą liczbę na czynniki?

Nie znamy szybkiego (wielomianowego) algorytmu na klasycznym komputerze - i właśnie na tym opiera się RSA. Algorytm Shora na komputerze kwantowym potrafiłby to zrobić szybko, ale takich maszyn o odpowiedniej skali jeszcze nie ma.

Q: Ile dzielników ma liczba 2^10?

Jedenaście: 1, 2, 4, ..., 1024. Ze wzoru (α + 1) dla α = 10.

Każdą liczbę naturalną $n > 1$ można zapisać jako iloczyn liczb pierwszych

$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k},$

i to dokładnie na jeden sposób (z dokładnością do kolejności czynników).

Co mówi twierdzenie

Liczby pierwsze są „cegiełkami”, z których zbudowane są wszystkie liczby naturalne. Twierdzenie mówi dwie rzeczy naraz:

istnienie - każdą liczbę da się rozłożyć na czynniki pierwsze;
jednoznaczność - taki rozkład jest tylko jeden.

Druga część brzmi jak oczywistość, ale nią nie jest. Nikt nie obiecywał, że rozkładając liczbę różnymi drogami, zawsze dojdziemy do tego samego wyniku. Na przykład

$60 = 6 \cdot 10 = 2 \cdot 3 \cdot 2 \cdot 5, \qquad 60 = 4 \cdot 15 = 2 \cdot 2 \cdot 3 \cdot 5,$

i rzeczywiście oba rozkłady dają $2^2 \cdot 3 \cdot 5$ - ale to trzeba udowodnić, a nie założyć. Niżej pokazujemy świat liczb, w którym ta własność nie zachodzi.

Dowód istnienia

Pokaż dowódUkryj dowód

Krok 1. Indukcja zupełna. Zakładamy, że każda liczba mniejsza od $n$ (i większa od $1$ ) ma rozkład na czynniki pierwsze. Pokażemy, że $n$ też.

Krok 2. Dwa przypadki. Jeśli $n$ jest pierwsza, to jest swoim własnym rozkładem - gotowe.

Krok 3. Liczba złożona. Jeśli $n$ nie jest pierwsza, to $n = a \cdot b$ dla pewnych $1 < a, b < n$ . Obie liczby są mniejsze od $n$ , więc na mocy założenia indukcyjnego mają rozkłady na czynniki pierwsze. Sklejając je, otrzymujemy rozkład liczby $n$ .

Krok 4. Wniosek. Zasada indukcji zupełnej kończy dowód. $\blacksquare$

Dowód jednoznaczności

Pokaż dowódUkryj dowód

Tu potrzebny jest lemat Euklidesa, który jest sercem całej sprawy.

Lemat Euklidesa. Jeśli liczba pierwsza $p$ dzieli iloczyn $ab$ , to dzieli $a$ lub dzieli $b$ .

Krok 1. Zakładamy nie wprost, że istnieje liczba mająca dwa różne rozkłady. Wybieramy najmniejszą taką liczbę $n$ :

$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s.$

Krok 2. Stosujemy lemat. Liczba pierwsza $p_1$ dzieli lewą stronę, więc dzieli też prawą, czyli iloczyn $q_1 \cdots q_s$ . Z lematu wynika, że $p_1$ dzieli któryś z czynników $q_j$ .

Krok 3. Dzielnik liczby pierwszej. Skoro $q_j$ jest pierwsza, a $p_1$ ją dzieli i jest większa od $1$ , to $p_1 = q_j$ .

Krok 4. Skracamy. Dzielimy obie strony przez $p_1$ . Otrzymujemy liczbę mniejszą od $n$ , która wciąż ma dwa różne rozkłady - wbrew temu, że $n$ była najmniejsza z taką własnością.

Krok 5. Sprzeczność kończy dowód: rozkład jest jednoznaczny. $\blacksquare$

Skąd bierze się lemat Euklidesa? Z algorytmu Euklidesa: jeśli $p \nmid a$ , to $\mathrm{NWD}(p, a) = 1$ , więc istnieją liczby całkowite $x, y$ takie, że $px + ay = 1$ . Mnożąc przez $b$ , dostajemy $pbx + aby = b$ - obie części lewej strony dzielą się przez $p$ (druga, bo $p \mid ab$ ), więc $p \mid b$ .

Dlaczego jedynka nie jest liczbą pierwszą

To nie jest kwestia gustu, tylko konsekwencja tego twierdzenia. Gdyby $1$ uznać za pierwszą, jednoznaczność natychmiast by padła:

$12 = 2^2 \cdot 3 = 1 \cdot 2^2 \cdot 3 = 1^2 \cdot 2^2 \cdot 3 = \ldots$

Rozkładów byłoby nieskończenie wiele. Definicja liczby pierwszej („dokładnie dwa dzielniki naturalne”) jest tak dobrana, by podstawowe twierdzenie arytmetyki pozostało prawdziwe.

Świat, w którym jednoznaczność zawodzi

Najlepszym dowodem na to, że twierdzenie nie jest oczywiste, jest przykład zbioru liczb, w którym jednoznaczność nie zachodzi. Rozważmy liczby postaci

$a + b\sqrt{-5}, \qquad a, b \in \mathbb{Z}.$

W tym świecie liczba $6$ ma dwa istotnie różne rozkłady na czynniki nierozkładalne:

$6 = 2 \cdot 3 = \left(1 + \sqrt{-5}\right)\left(1 - \sqrt{-5}\right).$

Żadnego z tych czynników nie da się rozłożyć dalej, a nie są one swoimi wielokrotnościami. Jednoznaczność przepadła.

To nie jest ciekawostka bez znaczenia. Dokładnie na tej pułapce wykładali się dziewiętnastowieczni matematycy „dowodzący” wielkiego twierdzenia Fermata: milcząco zakładali jednoznaczność rozkładu w pierścieniach liczb algebraicznych. Naprawił to Ernst Kummer, wprowadzając liczby idealne - i tak narodziła się teoria ideałów, jeden z filarów współczesnej algebry.

Po co to komu

NWD i NWW. Rozkład na czynniki pierwsze daje natychmiastowe wzory: największy wspólny dzielnik to iloczyn wspólnych czynników z najmniejszymi wykładnikami, a najmniejsza wspólna wielokrotność - wszystkich czynników z największymi.
Liczba dzielników. Dla $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ liczba dzielników wynosi $(\alpha_1 + 1)\cdots(\alpha_k + 1)$ . Na przykład $60 = 2^2 \cdot 3 \cdot 5$ ma $3 \cdot 2 \cdot 2 = 12$ dzielników.
Dowody niewymierności. To dzięki jednoznaczności rozkładu wiadomo, że $\sqrt{2}$ jest niewymierny.
Kryptografia. RSA opiera się na kontraście: rozkład istnieje i jest jedyny, ale dla dużych liczb nikt nie potrafi go szybko znaleźć. Bezpieczeństwo bierze się z tej różnicy między „istnieje” a „da się obliczyć”.

Kto i kiedy

Kluczowe elementy - lemat o liczbie pierwszej dzielącej iloczyn oraz jednoznaczność w wersji geometrycznej - znajdują się już w Elementach Euklidesa (księga VII, twierdzenie 30 i księga IX). Grecy nie dysponowali jednak notacją pozwalającą wypowiedzieć twierdzenie w dzisiejszej postaci.

Pierwsze pełne, nowoczesne sformułowanie wraz z dowodem podał Carl Friedrich Gauss w Disquisitiones Arithmeticae (1801) - książce, którą napisał w wieku $24$ lat i która ufundowała współczesną teorię liczb. To Gauss nadał twierdzeniu rangę „podstawowego”.

Najczęstsze pytania

Dlaczego jedynka nie jest liczbą pierwszą? Bo zniszczyłaby jednoznaczność rozkładu - każdą liczbę można by mnożyć przez dowolną potęgę jedynki. Definicja jest dobrana tak, by twierdzenie pozostało prawdziwe.

Czy zero i liczby ujemne mają rozkład? Twierdzenie dotyczy liczb naturalnych większych od $1$ . Dla ujemnych stosuje się je do wartości bezwzględnej, dopisując znak; zero rozkładu nie ma, bo dzieli się przez wszystko.

Czy jednoznaczność rozkładu to nie jest oczywiste? Nie - i najlepiej pokazuje to przykład pierścienia liczb $a + b\sqrt{-5}$ , w którym $6$ ma dwa różne rozkłady. Jednoznaczność jest własnością liczb całkowitych, a nie prawem natury.

Jak szybko można rozłożyć dużą liczbę na czynniki? Nie znamy szybkiego (wielomianowego) algorytmu na klasycznym komputerze - i właśnie na tym opiera się RSA. Algorytm Shora na komputerze kwantowym potrafiłby to zrobić szybko, ale takich maszyn o odpowiedniej skali jeszcze nie ma.

Ile dzielników ma liczba $2^{10}$ ? Jedenaście: $1, 2, 4, \ldots, 1024$ . Ze wzoru $(\alpha + 1)$ dla $\alpha = 10$ .

Podsumowanie

Każda liczba naturalna $n > 1$ ma rozkład na czynniki pierwsze i tylko jeden.
Istnienie dowodzi się indukcją zupełną, jednoznaczność - lematem Euklidesa i schodzeniem do najmniejszego kontrprzykładu.
Jedynka nie jest liczbą pierwszą właśnie po to, by jednoznaczność zachodziła.
Jednoznaczność nie jest oczywista: w pierścieniu $a + b\sqrt{-5}$ liczba $6$ ma dwa różne rozkłady - to potknięcie kosztowało dziewiętnastowiecznych matematyków wiele błędnych dowodów.
Praktyczne skutki: wzory na NWD i NWW, liczbę dzielników, dowody niewymierności oraz bezpieczeństwo RSA.