Předchozí část byla spíše pro zajímavost. Poznatky z této části už by ale bylo dobré míti v malíčku. Jako první si definujeme pojem dělitelnosti a násobku. Předpokládáme, že každý čtenář i čtenářka ví, co to znamená, když se řekne „4 dělí 32“ nebo „27 je násobek 3“ a podobně. V matematice je ale zvykem nespoléhat se na obecnou znalost a namísto toho si jednoznačně vymezit, co se jakým pojmem myslí. Jak si vysvětlíte v následující kapitole, obvyklým prostředkem jak zavést matematicky korektně pojem je definice. Zde si předvedeme, jak taková definice vypadá:
Nechť $a, b \in \Z$. Řekneme, že $a$ dělí $b$, značíme $a|b$, jestliže existuje $k \in \Z$ takové, že
V takovém případě říkáme, že $a$ je (celočíselný) dělitel $b$ a $b$ je (celočíselný) násobek $a$, případně také, že $b$ je dělitelné $a$. Pokud $a$ nedělí $b$, píšeme $a \!\nmid\! b$.
Když je to první pořádná definice, trochu se na ni podíváme. První věta „Nechť $a, b \in \Z$.“ zní trochu jako z přelomu 19. a 20. století a je pravda, že v jiném než matematickém textu se se slovíčkem „nechť“ moc nepotkáte. Jde ale o celkem běžný začátek definice a i jiných matematických formálních zápisů. Za tímto „retro“ slovem obvykle následují takzvané předpoklady definice, které říkají, co znamenají proměnné, se kterými definice pracuje. Zde zápis $a, b \in \Z$ značí, že proměnné $a$ a $b$ použité v definici zastupují nějaká (libovolná) celá čísla. O značce $\Z$ už ale předpokládáme, že je známá a v definici ji již nespecifikujeme.
Pak už je zaveden samotný pojem. Zde si přesně určujeme, co znamená, že řekneme např. „4 dělí 20“, neboli $4|20$ (ano, definice může zavést i to, jak se nový pojem značí). Podle definice snadno ověříme, že je tento výrok pravdivý (tj. splňuje podmínku z definice pro $a = 4$ a $b = 20$): za kýžené $k \in \Z$ v definici lze volit $k = 5$, neboť platí $a \cdot k = 4 \cdot 5 = 20 = b$.
Podle definice si také snadno ověříme, že pro každé celé číslo platí, že je toto číslo dělitelné samo sebou (volba $k = 1$) a že je dělitelné jedničkou (pro libovolné $b$ a $a = 1$ volba $k = b$). Každé celé číslo větší než jedna má tedy alespoň dva různé dělitele. Může jich mít více? Ano, může, dokonce o hodně více. Například nula jich má nekonečně mnoho, protože $a \cdot 0 = 0$ pro každé $a \in \Z$. Číslo 12 má (přirozených) dělitelů šest: 1, 2, 3, 4, 6 a 12. Obecně je počet přirozených dělitelů přirozeného čísla $n$ konečný a je menší než $n$ (dle definice nemůže $n$ mít dělitele většího než je $n$ samotné). Určit přesný počet dělitelů není úplně triviální úloha, neboť toto číslo se s hodnotou $n$ mění poměrně chaoticky. Například pro $12$ je to $6$, pro další číslo $13$ je to jen $2$ a pro $14$ je to zase $4$. Abychom tomu lépe porozuměli, podíváme se na ta čísla, která mají (v jistém smyslu) minimální počet dělitelů, tedy $2$. Tato čísla znáte pod pojmem prvočíslo.
Než si dle dobrého zvyku definujeme pojem prvočísla formálně a precizně, zdůrazněme, že následující definice vyžaduje, aby počet dělitelů byl právě $2$. To znamená, že číslo $1$ není prvočíslem, přestože „je dělitelné pouze jedničkou a samo sebou“. Bohužel pro jedničku jde ale o stejné číslo, takže různých dělitelů nemá dostatek a do exkluzivní společnosti prvočísel tak nepatří. Za upozornění také stojí to, že se omezujeme jen na přirozená čísla a to i v případě uvažovaných dělitelů. Kdybychom uvažovali i záporná čísla, pak by každé přirozené číslo mělo dvojnásobek dělitelů, protože by k nim patřila i jejich záporná varianta (např. každé číslo je dělitelné číslem $-1$).
Přirozené číslo $n \geq 2$ je prvočíslo, jestliže má právě dva přirozené dělitele: $1$ a $n$. Pokud $n \geq 2$ není prvočíslo, říkáme, že je složené.
Z definice vidíme, že jsme sice jedničce zapověděli příslušnost k prvočíslům, ale její výjimečnost to neoslabilo: jednička je jediné číslo, které je ani prvočíslem, ani složeným číslem.
O prvočíslech jsou napsané knihy a mnoho se o nich ví a překvapivě mnoho se o nich neví. My ale nechceme z této kapitoly udělat kapitolu nejdelší, takže si řekneme jen základní věci. Také se zatím nechceme pouštět do formálních důkazů (viz další kapitolu), takže tady některá tvrzení o prvočíslech uvedeme bez důkazu, případně důkaz odbudeme jen naznačením myšlenky. Hlavní věc, kterou byste si měli odnést, je to, že každé přirozené číslo (mimo jedničku) lze rozložit na součin prvočísel a že takové rozložení je jednoznačné. Také byste měli vědět, jak tento „prvočíselný rozklad“ souvisí s pojmy „nejmenší společný násobek“ a „největší společný dělitel“.
První tvrzení, které si uvedeme, je jednoduché, ale jeho důkaz je překvapivě komplikovaný5. Formálně si jej dokážete v předmětu BI(K)-DML: Diskrétní matematika a logika a my jej zde zcela vynecháme. Než si tvrzení zformulujeme „matematicky“, vyslovíme jej lidově: „Pokud prvočíslo dělí součin dvou čísel, pak musí dělit alespoň jedno z těchto čísel.“ Například víme, že prvočíslo $3$ dělí číslo $24 = 6 \cdot 4$, takže musí dělit alespoň jedno z čísel $6$ a $4$. Tvrzení, které nám říká, že toto je pravda pro libovolný součin dvou přirozených čísel, je známo jako Euklidovo lemma6. Mimochodem, požadavek na to, aby dělitel byl prvočíslem, nelze vynechat. Stačí si vzít místo $3$ složené číslo $8$. To také dělí součin $24 = 6 \cdot 4$, ale nedělí ani jedno z čísel $6$ a $4$. Rozmyslete si, proč tomu tak je.
Nechť $p$ je prvočíslo a nechť $a, b \in \mathbb{N}$ jsou taková, že $p | (a \cdot b)$. Pak platí, že $p | a$ nebo $p | b$.
Jelikož jde o naše první formální tvrzení, podíváme se na něj trochu podrobněji. Podobně jako definice začíná slovem „Nechť“, které opět uvádí předpoklady tvrzení. V tomto případě nám říká, že písemko $p$ v definici reprezentuje prvočíslo, tedy pojem zavedený v předchozí definici 1.2, a písemka $a$ a $b$ reprezentují libovolná přirozená čísla. O těchto třech číslech navíc předpokládáme, že splňují podmínku, že prvočíslo $p$ dělí součin $a \cdot b$. Tento předpoklad je v tvrzení zapsán pomocí značení zavedeného v definici 1.1. To je v matematice obvyklý postup: definice zavádí nové pojmy, o kterých pak zjišťujeme (tj. dokazujeme) nové matematické pravdy, které se dají zapsat jako tvrzení, věty, lemmata, apod. Viz následující kapitolu.
Už na základní škole, často už na prvním stupni, jste se učili, že každé přirozené číslo (mimo speciální jedničku) lze rozložit na součin prvočísel. Například číslo $12$ lze rozložit na součin prvočísel $2 \cdot 2 \cdot 3 = 2^2 \cdot 3$. Číslo $150$ lze rozložit na součin prvočísel $2 \cdot 3 \cdot 5^2$. a tak dále. Poněkud speciálně: prvočíslo, například $7$, je „součin jednoho prvočísla“ a to sebe samého, tedy například $7 = 7^1$. Proč tomu tak je? Naznačíme si to: Uvažujme číslo přirozené číslo $n \geq 2$. Pokud je $n$ prvočíslo, pak je rozložení na součin prvočísel hotovo. Pokud $n$ není prvočíslo, pak je složené a tedy existují přirozená čísla $n > a, b \geq 2$ taková, že $n = a \cdot b$. Nyní stejnou úvahu zopakujeme pro čísla $a$ a $b$. Pokud jsou obě prvočísla, máme hotovo. Pokud alespoň jedno z nich není prvočíslo, například $a$, pak je složené a existují přirozená čísla $a > c, d \geq 2$ taková, že $a = c \cdot d$ a tedy i $n = c \cdot d \cdot b$. V každém kroku rozkládáme menší čísla než předtím, takže tento proces nemůže pokračovat donekonečna. Musíme tedy nutně po konečném počtu kroků dojít k rozkladu na součin prvočísel. Toto je myšlenka důkazu existence rozkladu na součin prvočísel. Po přečtení kapitoly 2 si můžete tento důkaz zkusit udělat pořádně jako důkaz matematickou indukcí, bylo by to výborné cvičení. A nyní již slibované tvrzení, tentokráte nazvané „věta“, a to dokonce „Základní věta aritmetiky“:
Každé $n\in\N, n\geq 2,$ se dá jednoznačně vyjádřit ve tvaru součinu
kde $k\in\N$, $p_1 < p_2 < \cdots < p_k$ jsou prvočísla a $\alpha_1, \dots, \alpha_k\in\N$.
Tento zápis se nazývá prvočíselným rozkladem čísla $n$.
Opět se podíváme na tuto větu trochu podrobněji. Tentokrát nezačíná obstarožním „Nechť“, ale přímo formulací tvrzení, které se týká přirozeného čísla většího než jedna, pro které si v rámci věty zavedeme proměnnou $n$. Vysvětlení dalších značek je tentokrát až ve vedlejší větě za slůvkem „kde“, což je také obvyklá praxe. Všimněte si, že před spojkou „kde“ je čárka, jak velí pravidla českého pravopisu. V matematickém textu totiž i k matematickým výrazům přistupujeme jako by byly součástí textu, takže i nad matematikou mají pravidla českého pravopisu svou moc. Zkuste tuto informaci udržet až do doby, kdy budete psát bakalářskou práci.
Význam věty a v ní použitých značek si ukážeme na příkladu výše uvedeného čísla $150 = 2 \cdot 3 \cdot 5^2$. Písmenko $k$ udává počet různých prvočísel, které pro zapsání rozkladu potřebujeme. To je nejméně jedno (pro případ, kdy je $n$ prvočíslo nebo jeho mocnina) a nejvíce \ldots kolik vlastně? Pro dost velké číslo $n$ to může být hodně, ve skutečnosti neexistuje žádná horní hranice platná pro všechna možná $n$, proto dává smysl mít na $k$ jediný požadavek, tedy že to je přirozené číslo. Pro $n = 150$ je to ovšem $k= 3$, protože potřebujeme tři různá prvočísla $2, 3$ a $5$. Písmena $p_1, p_2, \ldots, p_k$ pak značí různá prvočísla použitá v rozkladu čísla $n$, kterých je $k$. Když potřebujete označit v matematice různé proměnné, jejichž počet je sám daný jinou proměnnou, je obvyklé použít (dolní) indexy, tedy ta číslíčka u písmene $p$ ve značení $p_1, p_2, \ldots, p_k$.
Důvod, proč je v zápisu prvočíselného rozkladu vyžadováno, aby byla prvočísla seřazena vzestupně ($p_1 < p_2 < \cdots < p_k$), je skrytý ve slově „jednoznačně“, které je v tvrzení použito. Kdyby tomu tak nebylo, mohli bychom napsat rozklad čísla $150$ i jako $3 \cdot 2 \cdot 5^2$ s $p_1 = 3$, $p_2 = 2$ a $p_3 = 5$, což je sice také rozklad na součin prvočísel, ale nesplňuje podmínku, že prvočísla jsou seřazena vzestupně. U zbývajících značek $\alpha_1, \ldots, \alpha_k$ si již vhodný komentář doplní čtenář či čtenářka sami jako pěkné a přínosné cvičení.
Pokud už v sobě máte dostatek zdravého matematického hnidopišství, možná si teď říkáte něco ve smyslu „Počkat, počkat! Tu jednoznačnost nejde takhle odbýt tím, že prvočísla seřadíme. My jsme si ukázali, proč rozklad existuje, ale z toho neplyne, že nemohou existovat dva různé obsahující různá prvočísla!“ Pokud jste si skutečně něco takového řekli, tak Vám gratulujeme, protože jste na správné cestě. Skutečně jsme si nic takového nedokázali. A ani dokazovat nebudeme, opět jen naznačíme. Můžete si důkaz opět dotáhnout k dokonalosti po přečtení kapitoly 2. Napovíme jen, že je dobré zvolit důkaz sporem a ukážeme myšlenku: Předpokládejme, že nějaké číslo $n$ má dva různé rozklady na součin prvočísel, pro jednoduchost předpokládejme, že na součin dvou:
kde $p_1 < p_2$ a $q_1 < q_2$ jsou prvočísla taková, že $p_1 \neq q_1$ a (tedy nutně i ) $p_2 \neq q_2$. Nyní přiskakuje na pomoc Euklidovo lemma 1.1, které nám říká, že $p_1$, které dělí $n = q_1q_2$ musí dělit $q_1$ nebo $q_2$. Jelikož ale $q_1$ a $q_2$ jsou dělitelná pouze jedničkou a sebou samými, musí být $p_1 = q_1$ nebo $p_1 = q_2$, což není možné: Nerovnost $p_1 \neq q_1$ jsme přímo předpokládali a rovnost $p_1 = q_2$ by nutně vedla na to, že $q_1 = p_2$ a to je spor s tím, že $p_1 < p_2$ a $q_1 < q_2$.
Uvažujme číslo 9000, které lze napsat jako součin $30\cdot 300$. Prvočíselný rozklad čísla 30 je $2 \cdot 3 \cdot 5$ a prvočíselný rozklad čísla 300 je $2^2 \cdot 3 \cdot 5^2$. Zápis prvočíselného rozkladu čísla 9000 je pak nutně součinem těchto dvou rozkladů, tedy $2^3 \cdot 3^2 \cdot 5^3$. Proč nutně? Protože určitě platí $9000 = 30 \cdot 300 = 2 \cdot 3 \cdot 5 \cdot 2^2 \cdot 3 \cdot 5^2 = 2^3 \cdot 3^2 \cdot 5^3$ a protože je prvočíselný rozklad jednoznačný. Jiný tedy už existovat nemůže.
Z předchozího příkladu je jasné, že dělitel nějakého čísla musí mít prvočíselný rozklad, který je v jistím smyslu „podmnožinou“ prvočíselného rozkladu daného čísla. S použitím značení z věty 1.1, pokud je $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ a $d$ je dělitel čísla $n$, pak prvočíselný rozklad čísla $d$ musí být ve tvaru
kde $0 \leq \beta_i \leq \alpha_i$ pro všechna $i = 1, \dots, k$. Připomínáme, že $\beta_i = 0$ znamená, že prvočíslo $p_i$ se v rozkladu čísla $d$ vůbec nevyskytuje, neboť „cokoli na nultou je jedna“.
Pro náš příklad s číslem 9000 je tedy prvočíselný rozklad jeho dělitelů ve tvaru $2^{\beta_1} \cdot 3^{\beta_2} \cdot 5^{\beta_3}$, kde $\beta_1 \in \{0, 1, 2, 3\}$, $\beta_2 \in \{0, 1, 2\}$ a $\beta_3 \in \{0, 1, 2, 3\}$. Například volba $\beta_1 = 2$, $\beta_2 = 0$ a $\beta_3 = 3$ dává dělitel $d = 2^2 \cdot 3^0 \cdot 5^3 = 4 \cdot 1 \cdot 125 = 500$. Volba $\beta_1 = \beta_2 = \beta_3 = 0$ dává dělitel $d = 2^0 \cdot 3^0 \cdot 5^0 = 1$ a volba $\beta_1 = 3$, $\beta_2 = 2$ a $\beta_3 = 3$ dává dělitel $d = 2^3 \cdot 3^2 \cdot 5^3 = 9000$. I když si kombinatoriky užijete zejména v kapitole 11, tak už nyní si můžete rozmyslet, že počet dělitelů čísla 9000 je $(3 + 1) \cdot (2 + 1) \cdot (3 + 1) = 4 \cdot 3 \cdot 4 = 48$.
Obecně platí následující věta, která je přímým důsledkem věty 1.1 a předchozí úvahy:
Nechť $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ je prvočíselný rozklad čísla $n \in \N, n \geq 2$. Pak počet přirozených dělitelů čísla $n$ je roven
Když už teď víme, jak vypadají dělitele daného čísla (známe-li jeho prvočíselný rozklad), můžeme se vrhnout na slíbené pojmy „největší společný dělitel“ a „nejmenší společný násobek“. Začneme tím, že si je definujeme.
Nechť $a, b \in \Z$. Největší společný dělitel čísel $a$ a $b$, značíme $\gcd(a, b)$, je největší přirozené číslo, které dělí obě čísla $a$ a $b$. Pro případ $a = b = 0$ definujeme $\gcd(0, 0) = 0$. Nejmenší společný násobek nenulových čísel $a$ a $b$, značíme $\lcm(a, b)$, je nejmenší přirozené číslo, které je násobkem obou čísel $a$ a $b$. Pokud je alespoň jedno z čísel $a$ a $b$ nulové, definujeme $\lcm(a, b) = 0$.
Zkratky $\gcd$ a $\lcm$ pochází z anglických slov „greatest common divisor“ a „least common multiple“ a používají se běžně i v českých textech, programovacích jazycích a podobně.
Jak určit největší společný dělitel dvou přirozených čísel $a$ a $b$? Existuje na to algoritmus nazývaný Euklidův algoritmus, který možná znáte a pokud ne, seznámíte se s ním v předmětu BI(K)-DML: Diskrétní matematika a logika. My si ukážeme, jak určit největší společný dělitel dvou čísel pomocí jejich prvočíselného rozkladu. Už víme, že dělitel je vlastně „podmnožinou“ prvočíselného rozkladu ve smyslu rovnice 1.5. Hledáme-li společného dělitele dvou čísel, pak hledáme dělitele, který je „podmnožinou“ obou prvočíselných rozkladů. No a chceme-li toho největšího, pak hledáme největší podmnožinu obou rozkladů, což je vlastně průnik těchto dvou podmnožin.
Co tím myslíme, si ukážeme na příkladu. Uvažujme čísla $a = 9000$ a $b = 8400$. Prvočíselný rozklad čísla $a$ je $2^3 \cdot 3^2 \cdot 5^3$ a prvočíselný rozklad čísla $b$ je $2^4 \cdot 3^1 \cdot 5^2 \cdot 7$. Největší společný dělitel musí obsahovat jen prvočísla, které jsou v obou rozkladech, v tomto případě tedy prvočísla $2,3$ a $5$. Aby byl největší možný, musí je obsahovat co nejvícekrát to lze. Například prvočíslo $2$ se v rozkladu čísla $a$ vyskytuje třikrát a v rozkladu čísla $b$ čtyřikrát, takže jej můžeme použít jen třikrát. Podobně prvočíslo $3$ se v rozkladu čísla $a$ vyskytuje dvakrát a v rozkladu čísla $b$ jednou, takže jej můžeme použít jen jednou. Prvočíslo $5$ se v rozkladu čísla $a$ vyskytuje třikrát a v rozkladu čísla $b$ dvakrát, takže jej můžeme použít jen dvakrát. Největší společný dělitel je tedy $2^3 \cdot 3^1 \cdot 5^2 = 8 \cdot 3 \cdot 25 = 600$.
Podobně lze určit i nejmenší společný násobek. Ten musí obsahovat všechna prvočísla, která se vyskytují v rozkladech obou čísel, tedy v našem případě $2,3,5$ a $7$. Aby byl nejmenší možný, musí je obsahovat co nejméněkrát, tedy tolikrát, kolikrát se vyskytuje v rozkladu čísla $a$ nebo v rozkladu čísla $b$, podle toho, kde se vyskytuje vícekrát. Prvočíslo $2$ se v rozkladu čísla $a$ vyskytuje třikrát a v rozkladu čísla $b$ čtyřikrát, takže jej musíme použít čtyřikrát. Prvočíslo $3$ se v rozkladu čísla $a$ vyskytuje dvakrát a v rozkladu čísla $b$ jednou, takže jej musíme použít dvakrát. Prvočíslo $5$ se v rozkladu čísla $a$ vyskytuje třikrát a v rozkladu čísla $b$ dvakrát, takže jej musíme použít třikrát. Prvočíslo $7$ se v rozkladu čísla $a$ nevyskytuje a v rozkladu čísla $b$ se vyskytuje jednou, takže jej musíme použít jednou. Nejmenší společný násobek je tedy $2^4 \cdot 3^2 \cdot 5^3 \cdot 7 = 16 \cdot 9 \cdot 125 \cdot 7 = 126000$.
Předchozí úvahu si nebudeme formalizovat do tvaru věty, i když by to šlo7. Měli byste ale chápat vztah, mezi prvočíselným rozkladem a pojmy největšího společného dělitele a nejmenšího společného násobku. Jako ověření toho, že Vaše pochopení je dostatečné si zkuste rozmyslet, proč platí následující vztah mezi těmito dvěma pojmy pro přirozená čísla $a$ a $b$:
Přirozené číslo $n \geq 2$ je prvočíslo, jestliže má právě dva přirozené dělitele: $1$ a $n$. Pokud $n \geq 2$ není prvočíslo, říkáme, že je složené.