Podstawowe twierdzenie arytmetyki

Podstawowe twierdzenie arytmetyki mówi nam, że każdą liczbę naturalną większą od 1 można jednoznacznie 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 można rozłożyć na iloczyn trzech liczb pierwszych 2 · 3 · 5, a liczbę 16 można rozłożyć na iloczyn czterech liczb pierwszych 2 · 2 · 2 · 2. Taki iloczyn liczb nazywany jest rozkładem na liczby pierwsze. Mówimy więc, że rozkład liczby 10 na liczby pierwsze to 2 · 5.

Same liczby pierwsze mają najprostszy rozkład na liczby pierwsze, ponieważ nie musimy ich dalej rozkładać. Rozkład liczby 7 na liczby pierwsze to po prostu 7.

Oblicz rozkład liczby pierwszej

Co mówi nam podstawowe twierdzenie arytmetyki

Podstawowe twierdzenie arytmetyki, czasami nazywane fundamentalnym twierdzeniem arytmetyki, mówi nam dwie rzeczy:

• dla dowolnej liczby naturalnej większej od 1 jesteśmy w stanie znaleźć rozkład na czynniki pierwsze,
• każda liczba ma dokładnie jeden unikalny rozkład na liczby pierwsze.

Udowodnijmy, że tak jest w istocie.

Dowód na istnienie

Najpierw udowodnimy, że dla każdej liczby naturalnej większej od 1 istnieje co najmniej jeden rozkład na liczby pierwsze. Wykorzystamy do tego indukcję matematyczną. Pierwszym krokiem indukcji matematycznej jest stwierdzenie, że najmniejsza liczba naturalna większa od 1, czyli liczba 2, jest pierwsza.

Teraz pokażemy, że skoro mamy ciąg liczb 2, …, n, dla którego można znaleźć rozkład na liczby pierwsze, to jeśli dodamy do tego ciągu liczbę n + 1, to dla tej nowej liczby istnieje rozkład na liczby pierwsze wykorzystujący liczby pierwsze z ciągu 2, …, n. Najpierw pokażmy to na przykładzie.

Na początku nasz ciąg 2, …, n jest nieco zdeformowany, ponieważ zawiera tylko jedną liczbę, liczbę 2. Mówimy, że jeśli dodamy liczbę n + 1, tj. liczbę 3, do tego ciągu, będzie istniał rozkład na liczby pierwsze dla tej liczby. Ponieważ liczba 3 jest liczbą pierwszą, oczywiście istnieje dla niej rozkład na liczby pierwsze - jest to liczba 3.

Nasz ciąg 2, …, n ma teraz dwa człony: 2, 3 Dodajmy do ciągu liczbę 4. Liczba 4 nie jest liczbą pierwszą, więc musi rozłożyć się na iloczyn dwóch innych liczb naturalnych, które są większe niż 1, ale mniejsze niż 4. Ale wszystkie takie liczby są częścią naszego ciągu! A jednak tylko liczby, które mają rozkład na liczby pierwsze, są w tym ciągu! Zatem nawet liczba 4 musi mieć rozkład na liczby pierwsze: 2 · 2.

Wracając do ogólnego dowodu, możemy napisać, że liczba 2 jest pierwsza, a zatem ma rozkład na liczby pierwsze. Załóżmy teraz, że każda liczba w ciągu 2, …, n może być rozłożona na liczby pierwsze - jest to nasze indukcyjne założenie. W takim razie albo liczba n + 1 jest liczbą pierwszą, a zatem może być trywialnie rozłożona na liczby pierwsze, albo jest liczbą złożoną. Zatem dla tej liczby muszą istnieć liczby a, b takie, że

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

przy czym musi być tak, że te liczby naturalne są naturalnie 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 być częścią ciągu 2, …, n. Ale w ten sposób dla każdej liczby w tym ciągu istnieje rozkład na liczby pierwsze (jest to nasze założenie indukcyjne), tj. 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 p_i i q_j są liczbami pierwszymi, a p₁ · p₂ · … · p_i i q₁ · q₂ · … · q_j są ich rozkładami na liczby pierwsze. Ale skoro powiedzieliśmy, że n + 1 jest rozkładalna na iloczyn n + 1 = a · b, to jednocześnie

$$\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}$$

Zatem liczba n + 1 jest rozkładalna na iloczyn liczb pierwszych p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, więc nowo dodana liczba n + 1 ma rozkład na liczby pierwsze. Wynika z tego, że każda liczba naturalna większa od 1 ma co najmniej jeden rozkład na liczby pierwsze.

Dowód jednoznaczności

Pokażmy teraz, że dla każdej liczby naturalnej większej od 1 nie istnieje więcej rozkładów pierwszych. Twierdzenie to udowodnimy za pomocą dowodu przez zaprzeczenie. Przyjmiemy, że twierdzenie nie jest prawdziwe, a zatem założymy, że istnieje liczba naturalna n większa od 1, która ma dwa różne rozkłady na liczby 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}$$

Przyjmiemy również, że spośród wszystkich liczb, które mają wiele rozkładów pierwszych, n jest najmniejsza. Oznacza to, że nie istnieje mniejsza liczba naturalna, która ma więcej niż jeden rozkład na liczby pierwsze. Ponieważ q₁ jest jedną z liczb pierwszych, która dzieli n, to oczywiście musi być również prawdą, że q₁ dzieli p₁ · p₂ · … · p_i.

Następnie musimy skorzystać z lematu Euklidesa. Mówi ona, że jeśli liczba pierwsza p dzieli iloczyn dwóch liczb całkowitych a · b, to p dzieli również co najmniej jedną z liczb a lub b. Na przykład, liczba pierwsza 3 dzieli liczbę 84. Możemy rozłożyć liczbę 84 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 jeśli q₁ dzieli p₁ · p₂ · … · p_i, to musi również dzielić co najmniej jedną z liczb p₁, p₂, … p_j. Można założyć - bez straty ogólności - że q₁ dzieli liczbę p₁. Tyle tylko, że p₁ też jest liczbą pierwszą. Kiedy liczba pierwsza może dzielić inną liczbę pierwszą? Na przykład, jaka liczba pierwsza jest podzielna przez 7? Ponownie, tylko liczba pierwsza 7. Nie może ona dzielić innej liczby pierwszej, ponieważ wtedy nie byłaby liczbą pierwszą. Zatem musi być prawdą, że p₁ = q₁.

Oznacza to, że w obu rozwinięciach pierwiastka istnieje jeden taki sam pierwiastek: pierwiastek p₁ i q₁. Podzielmy oba równania pierwiastków odpowiednio przez p₁ i 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₁, otrzymujemy tę samą liczbę po lewej stronie, oznaczmy ją na przykład przez m.

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

Po prawej stronie po prostu obcinamy 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 zdecydowanie liczbą naturalną, która jest mniejsza niż n, ponieważ liczba m została utworzona przez podzielenie liczby n przez jeden z jej czynników pierwszych. Ale po prawej stronie równań mamy czynnik pierwszy liczby m w obu przypadkach. W ten sposób byliśmy w stanie skonstruować inną liczbę m, która jest mniejsza niż n i która również ma dwa różne rozkłady na czynniki pierwsze. Jest to oczywiście sprzeczne z naszym założeniem, że n jest najmniejszą liczbą, która ma więcej niż jeden unikalny rozkład na czynniki pierwsze.

Jedynym wyjaśnieniem jest więc to, że nie istnieje "najmniejsza liczba z więcej niż jednym rozkładem na czynniki pierwsze". A to, że nie ma "najmniejszej liczby z więcej niż jednym rozkładem na czynniki pierwsze" oznacza, że nie ma liczby z wieloma rozkładami na czynniki pierwsze - więc każda liczba całkowita większa niż jeden ma dokładnie jeden unikalny rozkład na czynniki pierwsze.