Základní věta aritmetiky
Mezi odkazy starořeckých vědců, ze kterých matematika již více než dvě tisíciletí čerpá, patří kromě geometrie také poměrně ucelená a systematicky vystavěná teorie čísel. Jedním z jejich důležitých tvrzení je tzv. základní věta aritmetiky, jejíž znění společně s důkazem nacházíme již v Eukleidových Základech.
Tvrzení
V současné době větu formulujeme obyčejně takto:
Každé přirozené číslo větší než 1 je
- buď prvočíslem
- nebo je možné jej zapsat jako součin dvou či více prvočísel. Takový rozklad je přitom jednoznačně dán až na pořadí činitelů.
Jinými slovy nám toto tvrzení říká, že prvočísla jsou jakési základní kameny či atomy (tj. nedělitelné části) a ostatní přirozená čísla jsou z nich vystavěna pomocí operace násobení (mimo stojí číslo 1). Každé číslo můžeme pomocí dělení rozkládat na stále menší součásti až narazíme na prvočísla (která již dle definice dále rozložit nelze). Tvrzení nijak neomezuje opakovanou přítomnost jednoho či více prvočísel v rozkladu.
Mějme například číslo 280. To můžeme zapsat jako
280 = 8.35,
přičemž v rozkladu můžeme pokračovat, protože
8 = 2.4, 35 = 5.7 a nakonec 4 = 2.2.
Celkově tedy můžeme zapsat
280 = 2.2.2.5.7.
Protože víme, že při násobení čísel nezáleží na pořadí, mohli jsme činitele poskládat i odlišně, např. 280 = 2.5.2.7.2.
Abychom se v rozkladu čísla dobře orientovali (zvláště pokud je činitelů hodně), bývá zvykem opakované použití téhož prvočísla zapsat pomocí mocniny a jednotlivá prvočísla uvádět v rostoucím pořadí (tomuto tvaru se někdy říká kanonický), pro již zmíněné číslo 280 tedy máme
280 = 23.5.7.
Zápis rozkladu v kanonickém tvaru je již jednoznačný.
Faktorizace
Proces nalezení rozkladu na prvočíselné činitele (též prvočíselné faktory) se obyčejně nazývá faktorizace. Uvedená věta nám přitom dává jen omezený návod, jak prvočíselný rozklad hledat. Říká nám pouze, že pro složená čísla rozklad existuje, je jednoznačný a je složen výhradně z prvočísel. Nic více, nic méně.
Přitom se jedná o poměrně důležitou záležitost, kromě využití pro samotnou matematiku je to důležité i pro každodenní praxi. Řada kryptografických systémů (nejznámější je pravděpodobně RSA) používaných v informačních technologiích a telekomunikacích je založena mj. i na skutečnosti, že pro velmi velká čísla je nalezení jejich rozkladu výpočetně ohromně náročná úloha. Tak náročná, že její dokončení v rozumném čase i na nejrychlejších počítačích současnosti je nereálné.1)
Není proto překvapivé, že tyto záležitosti jsou intenzivně studovány, což vedlo i k vytvoření komplikovaných algoritmů, které se snaží rozklad velkých čísel provádět co možná nejefektivněji.
Při výuce středoškolské matematiky využíváme faktorizaci (pochopitelně jen u velmi malých čísel) při hledání největšího společného dělitele a nejmenšího společného násobku dvou čísel. K řešení těchto úkolů ale naštěstí máme k dispozici jednoduchý a účinný Eukleidův algoritmus.
Důkaz
Samotné tvrzení vypadá velmi samozřejmě a i ve středoškolské matematice jej běžně využíváme. Přestože jeho důkaz nevyžaduje žádné speciální dovednosti, není zcela triviální a vyžaduje jistou obezřetnost a pečlivost. Instruktivní může být i skutečnost, že používá i různé techniky (matematickou indukci, důkaz sporem).
Pokud je číslo prvočíslem, není co dokazovat, pro složená čísla důkaz provedeme ve dvou krocích. Jednodušší bude prokázat existenci prvočíselného rozkladu, trochu více úsilí pak budeme muset věnovat prokázání jednoznačnosti takového rozkladu.
Existence
Pro důkaz pomocí matematické indukce nejprve snadno ověříme, že tvrzení platí pro 2 (je prvočíslo). Indukční krok provedeme s výchozím předpokladem, že tvrzení platí pro všechna přirozená čísla od 2 až do u – 1. Pak u je buď prvočíslo (a tvrzení platí) nebo je u složené číslo. Musí tedy existovat přirozená čísla a a b (různá od 1), pro která platí u = a.b. Obě čísla a i b jsou nepochybně menší než u a tedy tvrzení věty pro ně (na základě předpokladu indukčního kroku) platí – jedná se buď o prvočísla nebo jejich prvočíselný rozklad existuje. Takže
a = p1. … .pm a b = q1. … .qn
pro nějaké sady prvočísel pi a qj. Pro součin pak ale můžeme psát
u = a.b = p1. … .pm.q1. … .qn,
takže prvočíselný rozklad existuje i pro u. Po počátečním ověření pro 2 je opakováním indukčního kroku tvrzení dokázáno pro všechna větší přirozená čísla.
Nyní již víme, že každé přirozené číslo větší než 1 je prvočíslem nebo existuje jeho prvočíselný rozklad.
Jednoznačnost
Budeme dokazovat sporem. Vyjdeme z předpokladu, že existují čísla s několika různými rozklady na prvočísla, a vybereme si z nich nejmenší takové číslo v. Platí tedy
v = p1. … .pm a zároveň v = q1. … .qn.
Pokud by se některý činitel pi rovnal některému qj, mohli bychom jím dělit v obou vyjádřeních pro v, čímž bychom dostali dva různé rozklady pro číslo menší než v. To nelze, protože v je nejmenší číslo s nejednoznačným rozkladem. Nyní již tedy víme, že pi ≠ qj pro všechna i a j (rozklady nemají žádného společného činitele).
Pokud je p1 < q1, provedeme prohození všech p a q, takže beze ztráty obecnosti máme p1 > q1 (dle předchozího odstavce stejné být nemohou). Můžeme tedy vytvořit číslo
w = (p1 – q1).p2. … .pm,
které je kladné a větší než 1. Vyjádření upravíme
w = v – q1.p2. … .pm = q1.q2. … .qn – q1.p2. … .pm = q1.(q2. … .qn – p2. … .pm).
Prvočíslo q1 dle posledního vztahu patří do jednoznačného rozkladu w (w je menší než v a tvrzení o jednoznačnosti rozkladu pro něj proto platí), případně je mu rovno (závorka musí být kladná, mohla by však být 1). Vzhledem k různosti od všech pi (viz výše) musí být také součástí rozkladu p1 – q1. To znamená, že pro nějaké přirozené k platí p1 – q1 = k.q1. Vyjádříme p1
p1 = (k + 1).q1,
což ukazuje na skutečnost, že se jedná o složené číslo. To je ale v rozporu s předpokladem, že p1 je prvočíslo.
Z nalezeného sporu vyplývá, že pro složené číslo neexistují dva různé prvočíselné rozklady.
Literatura
- Matematika – průvodce pro každého, Timothy Gowers, Dokořán (2006)
- Diskrétní matematika učební text, Zuzana Masáková – FJFI ČVUT Praha