Zasadnicze twierdzenie arytmetyki

Zasadnicze twierdzenie arytmetyki mówi nam, że każdą liczbę naturalną większą od 1 można w jednoznaczny sposób rozłożyć na iloczyn liczb pierwszych. Na przykład liczbę 15 można rozłożyć na iloczyn dwóch liczb pierwszych 3 · 5, liczbę 30 na iloczyn trzech liczb pierwszych 2 · 3 · 5, a choćby liczbę 16 na iloczyn czterech liczb pierwszych 2 · 2 · 2 · 2. Taki iloczyn nazywamy rozkładem na czynniki pierwsze. Mówimy więc, że rozkładem liczby 10 na czynniki pierwsze jest 2 · 5.

Najprostszy rozkład na czynniki pierwsze mają same liczby pierwsze, bo tych już dalej rozkładać nie trzeba. Rozkładem liczby 7 na czynniki pierwsze jest po prostu 7.

Co mówi zasadnicze twierdzenie arytmetyki

Zasadnicze twierdzenie arytmetyki, nazywane też podstawowym twierdzeniem arytmetyki, mówi nam więc dwie rzeczy:

• dla każdej liczby naturalnej większej od 1 potrafimy znaleźć rozkład na czynniki pierwsze,
• każda taka liczba ma dokładnie jeden rozkład na czynniki pierwsze.

Udowodnijmy, że naprawdę tak jest.

Dowód istnienia

Najpierw udowodnimy, że dla każdej liczby naturalnej większej od 1 naprawdę istnieje co najmniej jeden rozkład na czynniki pierwsze. Użyjemy do tego indukcji matematycznej. Pierwszym krokiem indukcji będzie stwierdzenie, że najmniejsza liczba naturalna większa od 1, czyli liczba 2, jest liczbą pierwszą.

Teraz pokażemy, że jeśli mamy już ciąg liczb 2, …, n, dla których da się znaleźć rozkład na czynniki pierwsze, i dołączymy do tego ciągu liczbę n + 1, to również dla tej nowej liczby istnieje rozkład na czynniki pierwsze. Najpierw pokażemy to na przykładzie.

Na początku nasz ciąg 2, …, n jest trochę nietypowy, bo zawiera tylko jedną liczbę, liczbę 2. Twierdzimy, że gdy dołączymy do tego ciągu liczbę n + 1, czyli liczbę 3, to dla tej liczby będzie istniał rozkład na czynniki pierwsze. Ponieważ 3 jest liczbą pierwszą, rozkład oczywiście istnieje — jest nim liczba 3.

Nasz ciąg 2, …, n ma teraz dwa wyrazy: 2, 3. Dołączamy do ciągu liczbę 4. Liczba 4 nie jest liczbą pierwszą, więc musi dać się rozłożyć na iloczyn dwóch innych liczb naturalnych, które są większe od 1, ale mniejsze od 4. Wszystkie takie liczby należą jednak do naszego ciągu! A w tym ciągu są tylko liczby, które mają rozkład na czynniki pierwsze! Zatem również liczba 4 musi mieć rozkład na czynniki pierwsze: 2 · 2.

Wróćmy do ogólnego dowodu. Możemy napisać, że liczba 2 jest liczbą pierwszą, a więc ma rozkład na czynniki pierwsze. Załóżmy teraz, że każdą liczbę z ciągu 2, …, n da się rozłożyć na czynniki pierwsze — to jest nasze założenie indukcyjne. Wtedy liczba n + 1 jest albo liczbą pierwszą, a więc w trywialny sposób rozkłada się na czynniki pierwsze, albo jest liczbą złożoną. Dla takiej liczby muszą więc istnieć liczby a, b takie, że

$$n+1=a\cdot b$$

przy czym te liczby naturalne muszą oczywiście być mniejsze od n + 1 i większe od 1:

$$\begin{eqnarray} a > 1,&\quad&a < n+1 \\ b > 1,&\quad&b < n+1 \\ \end{eqnarray}$$

Liczby a, b muszą więc należeć do ciągu 2, …, n. A dla każdej liczby z tego ciągu istnieje rozkład na czynniki pierwsze (to nasze założenie indukcyjne), czyli możemy napisać

$$\begin{eqnarray} a&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ b&=&q_1\cdot q_2 \cdot \ldots \cdot q_j\\ \end{eqnarray}$$

gdzie wszystkie p_i i q_j są liczbami pierwszymi, a p₁ · p₂ · … · p_i i q₁ · q₂ · … · q_j są ich rozkładami na czynniki pierwsze. Ponieważ jednak powiedzieliśmy, że n + 1 da się rozłożyć na iloczyn n + 1 = a · b, to zarazem zachodzi

$$\begin{eqnarray} n+1&=&a\cdot b\\ &=&p_1\cdot p_2 \cdot \ldots \cdot p_i\cdot q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

Liczbę n + 1 da się więc rozłożyć na iloczyn liczb pierwszych p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, czyli również nowo dołączona liczba n + 1 ma rozkład na czynniki pierwsze. Wynika z tego, że każda liczba naturalna większa od 1 ma co najmniej jeden rozkład na czynniki pierwsze.

Dowód jednoznaczności

Pokażmy teraz, że żadna liczba naturalna większa od 1 nie ma więcej niż jednego rozkładu na czynniki pierwsze. To twierdzenie udowodnimy za pomocą dowodu nie wprost. Założymy, że twierdzenie nie jest prawdziwe, czyli że istnieje liczba naturalna n większa od 1, która ma dwa różne rozkłady na czynniki pierwsze:

$$\begin{eqnarray} n&=&p_1\cdot p_2 \cdot \ldots \cdot p_i\\ n&=&q_1\cdot q_2 \cdot \ldots \cdot q_j \end{eqnarray}$$

Załóżmy przy tym, że spośród wszystkich liczb, które mają więcej rozkładów na czynniki pierwsze, n jest tą najmniejszą. To znaczy, że nie istnieje mniejsza liczba naturalna, która miałaby więcej niż jeden rozkład na czynniki pierwsze. Ponieważ q₁ jest jedną z liczb pierwszych, które dzielą liczbę n, to oczywiście musi też zachodzić, że q₁ dzieli liczbę p₁ · p₂ · … · p_i.

Dalej musimy skorzystać z lematu Euklidesa. Mówi on, że jeśli liczba pierwsza p dzieli iloczyn dwóch liczb całkowitych a · b, to p dzieli też co najmniej jedną z liczb a lub b. Przykład: liczba pierwsza 3 dzieli liczbę 84. Liczbę 84 możemy rozłożyć na iloczyn liczb 12 · 7. Lemat Euklidesa mówi, że liczba pierwsza 3 dzieli co najmniej jedną z liczb 12 lub 7 — w tym przypadku dzieli liczbę 12.

Korzystając z tego lematu, możemy powiedzieć, że skoro q₁ dzieli p₁ · p₂ · … · p_i, to musi też dzielić co najmniej jedną z liczb p₁, p₂, …, p_i. Możemy założyć — bez straty ogólności — że q₁ dzieli liczbę p₁. Tyle że p₁ też jest liczbą pierwszą. Kiedy liczba pierwsza może dzielić inną liczbę pierwszą? Na przykład: jaka liczba pierwsza dzieli się przez liczbę pierwszą 7? Znowu tylko liczba pierwsza 7. Nie może dzielić innej liczby pierwszej, bo wtedy tamta nie byłaby liczbą pierwszą. Musi więc zachodzić p₁ = q₁.

Oznacza to, że w obu rozkładach na czynniki pierwsze występuje ta sama liczba pierwsza: p₁, czyli q₁. Podzielmy oba równania przez p₁, czyli q₁:

$$\begin{eqnarray} \frac{n}{p_1}&=&\frac{p_1\cdot p_2 \cdot \ldots \cdot p_i}{p_1}\\ \frac{n}{q_1}&=&\frac{q_1\cdot q_2 \cdot \ldots \cdot q_j}{q_1} \end{eqnarray}$$

Ponieważ p₁ = q₁, po lewej stronie dostaniemy tę samą liczbę, oznaczmy ją na przykład m. Zachodzi więc

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

Po prawej stronie tylko skracamy ułamki:

$$\begin{eqnarray} m&=&p_2 \cdot p_3 \cdot \ldots \cdot p_i\\ m&=&q_2 \cdot q_3 \cdot \ldots \cdot q_j \end{eqnarray}$$

Liczba m jest na pewno liczbą naturalną mniejszą od liczby n, bo liczba m powstała przez podzielenie n przez jeden z jej czynników pierwszych. Po prawej stronie równań mamy jednak w obu przypadkach rozkład liczby m na czynniki pierwsze. Udało nam się więc skonstruować inną liczbę m, która jest mniejsza od liczby n i która też ma dwa różne rozkłady na czynniki pierwsze. To jest jednak sprzeczne z naszym założeniem, że n jest najmniejszą liczbą, która ma więcej niż jeden rozkład na czynniki pierwsze.

Jedynym wyjaśnieniem jest więc to, że nie istnieje żadna „najmniejsza liczba z więcej niż jednym rozkładem na czynniki pierwsze”. A to, że nie istnieje „najmniejsza liczba z więcej niż jednym rozkładem na czynniki pierwsze”, oznacza, że nie istnieje ani jedna liczba z wieloma rozkładami na czynniki pierwsze — każda liczba całkowita większa od jedynki ma więc dokładnie jeden rozkład na czynniki pierwsze.