Student World

Úvodní poznámka:
Následující důkaz jednoznačnosti rozkladu na prvočísla (základní věta aritmetiky) je dílem jednoho ze čtenářů Science Worldu, který chtěl ukázat, že toto tvrzení lze dokázat i prostředky středoškolské matematiky. Má tedy právě takovou podobu – bez formalismu typu seznamu axiomů na začátku apod. Nicméně postup jsme dali zkontrolovat a dva lidé s matematických vzděláním důkaz schválili jako správný.
Postup je ovšem stále poměrně dlouhý. S trochu odřenýma ušima lze tedy dále hájit i původní tvrzení o tom, že základní věta aritmetiky žádný "jednoduchý" důkaz nemá (viz http://www.scienceworld.cz/sw.nsf/ID/857B0DBF9E7887CDC12571E0007421B6).

***

1. Věta: Pro každé a, b z N platí: Každý společný násobek a a b je dělitelný nsn(a, b).
Důkaz: Uvažujme posloupnost čísel 0, 1, 2, … . Násobky a začínají nulou a pokračují vždy o a pozic dále. Násobky b obdobně o b pozic dále. První číslo (kromě nuly), které je dělitelné a i b, je nsn(a, b). Pokud skáčeme po násobcích a a b z čísla nsn(a, b), je situace zcela obdobná skákání z čísla 0, proto každý další společný násobek a a b bude o nsn(a, b) kroků dále.
2. Věta: Pro každé a, b z N platí: Pokud NSD(a, b) = 1, pak nsn(a, b) = a * b.
Důkaz sporem: Předpokládáme, že nsn(a, b) < a * b (větší být nemůže, protože a * b je také společným násobkem a a b). Pak podle 1 existuje k z {2, 3, …} takové, že nsn(a, b) = a * b / k. Protože nsn(a, b) je násobek a, musí b / k být z N, tedy k dělí b. Obdobně k dělí a. Tedy k je společný dělitel a a b, je však větší než 1, tedy nemůže platit předpoklad, že NSD(a, b) = 1.
3. Věta: Pro každé prvočíslo n a číslo a z {1, 2, …, n-1} platí: Čísla a a n jsou nesoudělná.
Důkaz sporem: Předpokládáme, že a a n jsou soudělná. Pak existují i, j z N a k z {2, 3, … } takové, že a = i * k a n = j * k. Číslo j musí být rovno 1, protože jinak by n nebylo prvočíslo. Pak k = n, takže a = i * n. To ale není možné, protože a je podle předpokladu menší než n.
4. Věta: Pro každé prvočíslo n a číslo a z {1, 2, …, n-1} platí, že nsn(a, n) = a * n.
Důkaz: Podle 3 je NSD(a, n) = 1. Podle 2 je nsn(a, n) = a * n.
5. Věta: Pro každé prvočíslo n a čísla a, b z {1, 2, …, n-1} platí, že n nedělí a * b.
Důkaz sporem: Předpokládáme, že n dělí a * b. Pak existuje k z N takové, že a * b = n * k. Označme x = a * b = n * k. Číslo x je tedy společný násobek čísel b a n, proto x >= nsn(b, n). Podle 4 je tedy a * b >= b * n, takže a >= n, což ale odporuje předpokladu.
6. Věta: Pro každé prvočíslo n a čísla a, b z N platí: Pokud n nedělí a a n nedělí b, pak n nedělí a * b.
Důkaz přímý: Předpokládáme, že n nedělí a a n nedělí b. Označme a = i * n + s, b = j * n + t, kde i, j jsou z N0 a s, t jsou z {1, 2, …, n-1}. Pak a * b = (i*n+s)(j*n+t) = i*j*n^2 + i*n*t + s*j*n + s*t = (i*j*n + i*t + s*j) * n + s * t. Proto n dělí a * b právě tehdy, když n dělí s * t. Podle 5 však n nedělí s * t, takže n nedělí ani a * b.
7. Věta: Pro každé prvočíslo n a čísla a, b z N platí: Pokud n dělí a * b, pak n dělí a nebo n dělí b.
Důkaz: Jde o obměnu implikace 6.
8. Věta: Pro každé prvočíslo n a čísla a1, a2, …, am z N platí. Pokud n dělí a1*a2*…*am, pak existuje i z {1, 2, …, m} takové, že n dělí ai.
Důkaz přímý: Předpokládáme, že n dělí a1*a2*…*am. Pro m = 1 je důkaz triviální. Pro m >= 2 označme: b = a2*a3*…*am. Pak n dělí a1 * b. Podle 7 pak n dělí a1 nebo n dělí b. Pokud n dělí a1, pak i je 1 a tvrzení je dokázáno. Pokud n nedělí a1, pak n dělí b, tj. n dělí a2*a3*…*am a opakujeme postup pro kratší posloupnost a2, a3, …, am.
9. Věta: Pro každé prvočíslo n a prvočíselný rozklad p1, p2, …, pm čísla x z N platí: Pokud n dělí x, pak existuje i z {1, 2, …, m} takové, že pi = n.
Důkaz přímý: Předpokládáme, že n dělí x. Podle 8 existuje i z {1, 2, …, m} takové, že n dělí pi. Pak ale musí být přímo pi = n, protože pi je prvočíslo.
10. Věta: Pro každé x z {2, 3, 4, …} platí: Všechny prvočíselné rozklady čísla x jsou stejné.
Důkaz: Mějme dva prvočíselné rozklady čísla x: a1, a2, …, am a b1, b2, …, bn. Pro m=1 je x prvočíslo a tedy b1=x=a1. Pro m>=2 pokračujeme: Je zřejmé, že a1 dělí x. Podle 9 existuje i z {1, 2, …, n} takové, že bi = a1. Nyní stačí dokázat, že rozklady jsou shodné po odebrání a1 a bi, na což lze použít induktivně tuto větu.

autor Petr Šlechta