Základní věta aritmetiky

Základní věta aritmetiky nám říká, že každé přirozené číslo větší než 1 lze jednoznačně rozložit na součin prvočísel. Například číslo 15 lze rozložit na součin dvou prvočísel 3 · 5, číslo 30 lze rozložit na součin tří prvočísel 2 · 3 · 5 a třeba číslo 16 lze rozložit na součin čtyř prvočísel 2 · 2 · 2 · 2. Takové součinu čísel pak říkáme prvočíselný rozklad. Říkáme tedy, že prvočíselný rozklad čísla 10 je 2 · 5.

Pusťte si video verzi článku!

Nejjednodušší prvočíselný rozklad mají samotný prvočísla, protože ty už dále rozkládat nemusíme. Prvočíselným rozkladem čísla 7 je zkrátka 7.

Spočítejte si prvočíselný rozklad

Co nám říká základní věta aritmetiky

Základní věta aritmetiky, někdy též zvaná fundamentální věta aritmetiky, nám tedy říká dvě věci:

• pro každé přirozené číslo větší než 1 jsme schopni prvočíselný rozklad nalézt,
• každé číslo má právě jeden unikátní prvočíselný rozklad.

Pojďme si dokázat, že to tak opravdu je.

Důkaz existence

Nejprve dokážeme, že pro každé přirozené číslo větší než 1 opravdu existuje alespoň jeden prvočíselný rozklad. Použijeme k tomu matematickou indukci. Prvním krokem matematické indukce bude, že si řekneme že nejmenší přirozené číslo, které je větší než 1, to jest číslo 2, je prvočíslo.

Nyní ukážeme, že když už máme posloupnost čísel 2, …, n, pro které lze nalézt prvočíselný rozklad, tak když k této posloupnosti přidáme číslo n + 1, tak pro toto nové číslo existuje prvočíselný rozklad pomocí prvočísel z posloupnosti 2, …, n. Nejdříve si to ukážeme na příkladě.

Na začátku je naše posloupnost 2, …, n trochu deformovaná, protože obsahuje jen jedno číslo, číslo 2. My říkáme, že když k této posloupnosti přidáme číslo n + 1, tj. číslo 3, tak pro toto číslo bude existovat prvočíselný rozklad. Protože číslo 3 je prvočíslem, tak pro něj prvočíselný rozklad samozřejmě existuje — je to číslo 3.

Naše posloupnost 2, …, n má teď dva členy: 2, 3. Přidáme do posloupnosti číslo 4. Číslo 4 není prvočíslem, musí jít tedy rozložit na součin dvou jiných přirozených čísel, která jsou větší než 1, ale menší než 4. Všechny taková čísla jsou ale součástí naší posloupnosti! A přitom v této posloupnosti jsou jen čísla, které mají prvočíselný rozklad! Tedy, i číslo 4 musí mít prvočíselný rozklad: 2 · 2.

Když se vrátíme k obecnému důkazu, tak můžeme napsat, že číslo 2 je prvočíslo a tedy má prvočíselný rozklad. Předpokládejme nyní, že každé číslo z posloupnost 2, …, n lze prvočíselně rozložit — to je náš indukční předpoklad. Potom platí, že číslo n + 1 je buď prvočíslo a tedy lze triviálně rozložit na prvočísla anebo je to složené číslo. Pro toto číslo tak musí existovat čísla a, b taková, že

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

přitom musí platit, že tato přirozená čísla jsou samozřejmě menší než n + 1 a větší než 1:

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

Čísla a, b tak musí být součástí posloupnosti 2, …, n. Přitom ale pro každé číslo z této posloupnosti existuje prvočíselný rozklad (je to náš indukční předpoklad), tj. můžeme napsat

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

Kde všechna p_i a q_j jsou prvočísla a p₁ · p₂ · … · p_i a q₁ · q₂ · … · q_j jsou tak jejich prvočíselné rozklady. Protože jsme ale řekli, že n + 1 je rozložitelné na součin n + 1 = a · b, tak zároveň platí

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

Číslo n + 1 tedy je rozložitelné na součin prvočísel p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, tedy i nově přidané číslo n + 1 má prvočíselný rozklad. Z toho plyne, že každé přirozené číslo větší než 1 má alespoň jeden prvočíselný rozklad.

Důkaz unikátnost

Ukažme si nyní, že pro každé přirozené číslo větší než 1 neexistuje více prvočíselných rozkladů. Tuto větu dokážeme pomocí důkazu sporem. Budeme předpokládat, že věta není pravdivá a tedy budeme předpokládat, že existuje přirozené číslo n větší než 1, které má dva různé prvočíselný rozklady:

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

Zároveň předpokládejme, že ze všech čísel, které mají více prvočíselných rozkladů, je n to nejmenší. Tzn., že neexistuje menší přirozené číslo, které by mělo více než jeden prvočíselný rozklad. Protože q₁ je jedním z prvočísel, které dělí číslo n, tak musí samozřejmě také platit, že q₁ dělí číslo p₁ · p₂ · … · p_i.

Dále musíme použít Euklidovo lemma. To říká, že pokud prvočíslo p dělí součin dvou celých čísel a · b, tak potom p také dělí alespoň jedno z čísel a nebo b. Pro příklad: prvočíslo 3 dělí číslo 84. Číslo 84 můžeme rozložit na součin čísel 12 · 7. Euklidovo lemma říká, že prvočíslo 3 dělí alespoň jedno z čísel 12 nebo 7 — v tomto případě dělí číslo 12.

Za použití tohoto lemma můžeme říci, že když q₁ dělí p₁ · p₂ · … · p_i, tak musí také dělit alespoň jedno z čísel p₁, p₂, … p_j. Může předpokládat — bez újmy na obecnosti — že q₁ dělí číslo p₁. Jenomže p₁ je také prvočíslo. Kdy může prvočíslo dělit jiné prvočíslo? Například, jaké prvočíslo je dělitelné prvočíslem 7? Zase jedině prvočíslo 7. Nemůže dělit jiné prvočíslo, protože potom by to nebylo prvočíslo. Musí tedy platit, že p₁ = q₁.

Znamená to, že v obou prvočíselných rozkladech existuje jedno prvočíslo, které je stejné: prvočíslo p₁, respektive q₁. Pojďme obě prvočíselné rovnice vydělit p₁, respektive 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}$$

Protože p₁ = q₁, tak na levé straně dostaneme stejné číslo, označme si ho třeba m. Platí tedy, že

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

Na pravé straně jen pokrátíme zlomky:

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

Číslo m je určitě přirozené číslo, které je menší než číslo n, protože číslo m vzniklo tak, že jsme vydělili n jedním z jeho prvočinitelů. Na pravé straně rovnic máme ale v obou případech prvočíselný rozklad čísla m. Tedy, dokázali jsme sestrojit jiné číslo m, které je menší než číslo n a které má také dva různé prvočíselné rozklady. Což je ovšem ve sporu s naším předpokladem, že n je nejmenší číslo, která má více než jeden unikátní prvočíselný rozklad.

Jediné vysvětlení tedy je, že neexistuje žádné „nejmenší číslo s více než jedním prvočíselným rozkladem“. A to, že neexistuje „nejmenší číslo s více než jedním prvočíselným rozkladem“ znamená, že neexistuje ani jedno číslo, s více prvočíselnými rozklady — každé celé číslo větší než jedna tedy má právě jeden unikátní prvočíselný rozklad.