Další příklad grupy: grupa (Dn, ◦) Příklad. Nechť n ≥ 3 je přirozené číslo a představme si pravidelný n-úhelník. Označme Dn množinu všech shodností tohoto n-úhelníka, tedy zobrazení, která zachovávají délky úseček a kterými je náš n-úhelník zobrazen sám na sebe. Pak Dn má 2n prvků, z toho n rotací kolem středu n-úhelníka (včetně identity – rotace o nulový úhel) a n osových souměrností (vzhledem k osám procházejících středem n-úhelníka a také dvěma z vrcholů a středů stran). Náčrtek. Snadno se ověří, že vzhledem ke skládání dostáváme nekomutativní grupu (Dn, ◦). Každá shodnost permutuje množinu vrcholů n-úhelníka, přičemž různým shodnostem odpovídají různé permutace vrcholů. Proto, očíslujeme-li vrcholy n-úhelníka po řadě čísly 1, 2, . . . , n, lze každou shodnost n-úhelníka ztotožnit s prvkem grupy Sn. Rotace jsou ztotožněny s mocninami cyklu (1, 2, . . . , n), každá osová souměrnost je ztotožněna se složením několika nezávislých transpozic. Dělitelnost v Z Definice. Říkáme, že celé číslo b ∈ Z je dělitelem celého čísla a ∈ Z, píšeme b | a, existuje-li c ∈ Z tak, že a = b · c. Věta (o dělení se zbytkem). Pro každé a ∈ Z a m ∈ N existuje jediná dvojice čísel q, r ∈ Z takových, že a = m · q + r a současně 0 ≤ r < m. Důkaz. Definice. Číslo q se nazývá (neúplný) podíl a číslo r zbytek po dělení čísla a číslem m. Definice. Společným dělitelem čísel a, b ∈ Z rozumíme každé číslo c ∈ Z splňující c | a a současně c | b. Je-li alespoň jedno z čísel a, b nenulové, existuje jen konečně mnoho jejich společných dělitelů; největší z nich se nazývá největší společný dělitel čísel a, b, značíme jej (a, b). Jestliže naopak a = b = 0, je jejich největší společný dělitel definován jako nula, tj. (0, 0) = 0. Poznámka. Zřejmě platí (a, b) = (|a|, |b|) a (a, 0) = |a|, zaměříme se proto na největší společný dělitel přirozených čísel a, b. Euklidův algoritmus Pro daná a, b ∈ N provádějme postupné dělení se zbytkem: a = b · q0 + r0 b = r0 · q1 + r1 r0 = r1 · q2 + r2 r1 = r2 · q3 + r3 ... rn−3 = rn−2 · qn−1 + rn−1 rn−2 = rn−1 · qn + rn rn−1 = rn · qn+1 + 0 Přitom b > r0 > r1 > r2 > . . . , proto skutečně po několika děleních nastane rn+1 = 0. Věta. Pro libovolná a, b ∈ N platí (a, b) = rn. Důkaz. Věta (Bezoutova rovnost). Pro libovolná a, b ∈ Z existují u, v ∈ Z tak, že (a, b) = u · a + v · b. Důkaz. Nejmenší společný násobek Definice. Společným násobkem čísel a, b ∈ Z rozumíme každé číslo c ∈ Z splňující a | c a současně b | c. Poznámka. Je-li a = 0 nebo b = 0, je jediným společným násobkem čísel a, b číslo 0. V opačném případě existují kladné společné násobky, například |a · b|. Definice. Jsou-li obě čísla a, b ∈ Z nenulová, rozumíme nejmenším společným násobkem čísel a, b nejmenšího ze všech kladných společných násobků těchto čísel. Je-li alespoň jedno z čísel a, b nulové, definujeme nejmenší společný násobek čísel a, b jako nulu. Věta. Nechť a, b ∈ Z, a = 0 = b. Pak nejmenším společným násobkem čísel a, b je číslo |a·b| (a,b) . Pro libovolné číslo c ∈ Z platí, že c je společným násobkem čísel a, b, právě když c je dělitelné nejmenším společným násobkem čísel a, b. Důkaz. Poznámka. Druhá část předchozí věty platí i v případě, kdy je některé z čísel a, b nulové. Další důsledky Bezoutovy rovnosti Věta (Bezoutova rovnost). Pro libovolná a, b ∈ Z existují u, v ∈ Z tak, že (a, b) = u · a + v · b. Následující důsledek vysvětluje, proč jsme dodefinovali (0, 0) = 0. Důsledek. Pro libovolná a, b, d ∈ Z platí d | (a, b) ⇐⇒ d | a, d | b. Důkaz. Definice. Čísla a, b ∈ Z se nazývají nesoudělná, jestliže (a, b) = 1. Důsledek. Čísla a, b ∈ Z jsou nesoudělná, právě když existují u, v ∈ Z tak, že u · a + v · b = 1. Důsledek. Pro libovolná a, b, c ∈ Z platí a | b · c, (a, b) = 1 =⇒ a | c. Důkaz. Definice. Přirozené číslo p se nazývá prvočíslo, jestliže jeho jediným dělitelem větším než 1 je p samotné. Věta. Pro libovolné prvočíslo p a libovolná b, c ∈ Z platí p | b · c =⇒ p | b nebo p | c. Věta (o jednoznačném rozkladu v Z). Libovolné celé číslo a > 1 je buď prvočíslo, nebo jej lze napsat jako součin několika prvočísel, a to jednoznačně až na pořadí činitelů. Důkaz. Důsledek. Prvočísel je nekonečně mnoho. Důsledek. Čísla a, b ∈ Z jsou nesoudělná, právě když neexistuje prvočíslo p dělící a i b. Důkaz. Poznámka. Předchozí větu lze pro malá přirozená čísla užít k hledání největšího společného dělitele tak, že obě čísla rozložíme na součin prvočísel a zjistíme, která prvočísla se vyskytují v obou rozkladech. Obecně však nalézt rozklad na prvočinitele je mnohem obtížnější úkol než nalézt největšího společného dělitele. Celý systém bezpečné komunikace v současnosti je založen na tom, že neumíme rozložit přirozené číslo, které je součinem dvou velkých (řekněme 150-ciferných) prvočísel (výpočet, který by trval několik století, je z praktického hlediska pochopitelně bezcenný). Kongruence, zbytkové třídy Definice. Nechť m ∈ N, a, b ∈ Z. Říkáme, že a, b jsou kongruentní modulo m, a píšeme a ≡ b (mod m), jestliže m | a − b. Poznámka. Zřejmě a ≡ b (mod m), právě když a, b mají stejný zbytek po dělení číslem m. Definice. Nechť m ∈ N. Pro libovolné a ∈ Z definujeme množinu [a]m = {a + k · m; k ∈ Z}, kterou nazýváme zbytková třída modulo m obsahující a. Poznámka. Množina [a]m = {a + k · m; k ∈ Z} se skládá z právě těch celých čísel, která mají stejný zbytek po dělení číslem m jako číslo a. Věta. Pro libovolná a, b ∈ Z, m ∈ N nastává [a]m = [b]m právě tehdy, když a ≡ b (mod m). Důkaz. Označení. Množinu všech zbytkových tříd podle modulu m ∈ N značíme Zm. Je tedy Zm = {[0]m, [1]m, [2]m, . . . , [m − 1]m}. Operace na množině Zm Věta. Nechť m ∈ N, a, b, c, d ∈ Z jsou libovolná. Jestliže platí [a]m = [c]m, [b]m = [d]m, pak také [a + b]m = [c + d]m, [a · b]m = [c · d]m. Důkaz. Důsledek. Nechť m ∈ N. Vztahy [a]m + [b]m = [a + b]m, [a]m · [b]m = [a · b]m pro libovolná a, b ∈ Z definují operace + a · na množině Zm. Věta. Pro libovolné m ∈ N je (Zm, +) komutativní grupa s neutrálním prvkem [0]m, v níž inverzním prvkem k libovolné třídě [a]m je třída [−a]m. Věta. Pro libovolné m ∈ N je (Zm, ·) komutativní pologrupa s neutrálním prvkem [1]m. Poznámka. Jestliže m > 1, pro každé a ∈ Z platí [a]m · [0]m = [a · 0]m = [0]m = [1]m, a tedy (Zm, ·) není grupa. Grupa (Z× m, ·) Věta. Nechť m ∈ N, a ∈ Z jsou libovolná. Zbytková třída [a]m má inverzní prvek v pologrupě (Zm, ·), právě když celá čísla a, m jsou nesoudělná. Důkaz. Označení. Pro libovolné m ∈ N označme Z× m množinu všech zbytkových tříd [a]m, které mají inverzní prvek v pologrupě (Zm, ·), tedy Z× m = {[a]m; a ∈ Z, (a, m) = 1}. Důsledek. Pro každé m ∈ N je (Z× m, ·) komutativní grupa. Označení. Pro libovolné m ∈ N označme ϕ(m) počet všech přirozených čísel nepřevyšujících m, která jsou nesoudělná s m, tedy ϕ(m) = |{a ∈ Z; 0 < a ≤ m, (a, m) = 1}|. Důsledek. Pro libovolné m ∈ N platí |Z× m| = ϕ(m). Definice. Výše definované zobrazení ϕ : N → N se nazývá Eulerova funkce. Příklad.