1.10./5.10.

1. Euklidův algoritmus

Nechť a_{0} ≥ a_{1} jsou dvě přirozená čísla. Připomeňme Euklidův algoritmus hledání největšího společného dělitele (NSD) čísel a_{0} a a_{1}:

Známe-li a_{i−1} a a_{i} spočteme a_{i+1} = (a_{i−1})mod a_{i}. Tedy víme, že existuje takové q_{i} ∈ N a a_{i+1} < a_{i}, že a_{i−1} = q_{i}a_{i} +a_{i+1} . Algoritmus skončí, když a_{n+1} = 0, potom a_{n} = NSD(a_{0}, a_{1}).

1.1. Najděte pomocí Euklidova algoritmu největší společný dělitel čísel 72 a 93. Najděte dále taková celá čísla x a y, aby NSD(72, 93) = x · 72 + y · 93.

První část úkolu je snadná, sepišme si i jakým způsobem jednotlivé zbytky po celočíselném dělení získáme:

a_{0} = 93, a_{1} = 72, a_{2} = 93 − 72 = 21, a_{3} = 72 − 3 · 21 = 9, a_{4} = 21 − 2 · 9 = 3 = NSD(93, 72) a_{5} = 0. Druhou část úlohy vyřešíme rovněž pomocí Euklidova algoritmu, stačí si uvě-

domit, že každé z čísel a_{i+1} dostaneme jako celočíselnou lineární kombinaci dvou předchozích hodnot a_{i−1} a a_{i}. Jednoduchou indukční úvahou zjistíme, že každé číslo a_{i+1} je celočíselnou lineární kombinaci hodnot a_{0} a a_{1}. Konkrétně:

a_{2} = 21 = 93 − 72, a_{3} = 9 = 72 − 3 · 21 = 72 − 3 · (93 − 72) = 4 · 72 − 3 · 93, a_{4} = 3 = NSD(93, 72) = 21 − 2 · 9 = (93 − 72) − 2 · (4 · 72 − 3 · 93) = 7 · 93 − 9 · 72. Zjistili jsme, že x = −9 a y = 7. □

1.2. Najděte celá čísla x a y tak, aby x · 18 + y · 25 = 1.

Protože NSD(18, 25) = 1, zaručuje nám Euklidův algoritmus existenci požadovaných čísel x, y ∈ Z. Použijeme ho tedy (podobně jako v předchozí úloze) i k jejich nalezení:

a_{0} = 25, a_{1} = 18, a_{2} = 7 = 25 − 18, a_{3} = 4 = 18 − 2 · 7 = 18 − 2 · (25 − 18) = 3 · 18 − 2 · 25, a_{4} = 3 = 7 − 4 = 25 − 18 − (3 · 18 − 2 · 25) = 3 · 25 − 4 · 18, a_{5} = NSD(25, 18) = 1 = 4 − 3 = 3 · 18 − 2 · 25 − (3 · 25 − 4 · 18) = 7 · 18 − 5 · 25. □

1.3. Najděte všechna celočíselná řešení rovnice x · 18 + y · 25 = 1.

V předchozím příkladě jsme našli jedno řešení, označme ho (x_{0}, y_{0}). Uvažujme nyní libovolné další řešení (x, y). Stejnou úvahou jako při hledání všech řešení lineárních rovnic nad tělesem dostaneme

(x − x_{0}) · 18 + (y − y_{0}) · 25 = 0.

Všechna racionální řešení této rovnice jsou tvaru (q ·25, −q ·18), kde q ∈ Q. Protože 25 a 18 jsou nesoudělná, tvoří celočíselné dvojice řešení dané homogenní rovnice právě dvojice (c · 25, −c · 18) pro c ∈ Z. Tedy jsme zjistili, že platí (x − x_{0}) = c.25 a (y − y_{0}) = −c.18 pro vhodné celé c, proto {(7 + c · 25, −5 − c · 18)| c ∈ Z} tvoří množinu všech celočíselných řešení rovnice. □

1.4. Najděte všechna celočíselná řešení rovnice x · 18 + y · 25 = 10.

Vynásobíme-li již vyřešenou rovnici 7 · 18 − 5 · 25 = 1 desítkou, okamžitě vidíme, že rovnici x · 18 + y · 25 = 10 řeší x = 10 · 7 = 70 a y = −5 · 10 = −50. Úvaha, kterou nalezneme všechna řešení bude zcela stejná jako v předchozím příkladě (a analogická hledání řešení nehomogenní soustavy rovnic nad tělesem). Tedy množina všech celočíselných řešení rovnice je tvaru {(70 + c · 25, −50 − c · 18)| c ∈ Z}. □

1.5. Najděte všechna celočíselná řešení rovnice x · 18 + y · 24 = 10.

Protože NSD(18, 24) = 6, musela by pro libovolné celočíselné řešení rovnice x · 18 + y · 24 = 10 šestka dělit její levou a proto i pravou stranu. Ovšem 6 nedělí 10, proto množina všech celočíselných řešení zadané rovnice je prázdná. □

1.6. Najděte všechna celočíselná řešení rovnice x · 18 + y · 24 = 12.

Tentokrát vidíme, že NSD(18, 24)/12, můžeme tedy celou rovnici vydělit hodnotou NSD(18, 24) (= 6) a řešit upravenou rovnici x·3+y·4 = 2. Snadno nahlédneme, že (2, −1) je jedním řešením rovnice, a protože jsou čísla 3 a 4 nesoudělná, je množina všech celočíselných řešení tvaru {(2 + c · 4, −1 − c · 3)| c ∈ Z}. □

1.7. Najděte všechna celočíselná řešení rovnice x · 18 − y · 24 + 6 = 0.

Obvyklým způsobem zjistíme, že , že −1 · 18 + 1 · 24 = 6, což snadno upravíme na tvar 1 · 18 − 1 · 24 + 6 = 0. Našli jsme tedy jedno řešení (1, 1) diofantické rovnice. Nyní obvyklou lineárně algebraickou úvahou najdeme celočíselná řešení homogenní soustavy x · 18 − y · 24 = 0, jíž jsou právě celočíselné násobky vektoru (4, 3), tedy množina všech celočíselných řešení tvaru {(1 + c · 4, 1 + c · 3)| c ∈ Z}. □

Pozorování 1.8. V předchozích úlohách jsme našli obecně fungující algoritmus, pro popis množiny všech celočíselných řešení (tzv. lineární diofantické) rovnice ax+ by = c, kde a, b, c ∈ N. Nejprve najdeme Euklidovým algoritmem NSD(a, b). Jestliže NSD(a, b)/c, najdeme rozšířeným Euklidovým algoritmem jedno řešení (x_{0}, y_{0}) a množina všech celočíselných řešení je tvaru \{(x_{0} + \frac{b·c}{NSD (a,b)} , y_{0} − \frac{a·c}{NSD (a,b)} )| c ∈ Z\}. Jestliže NSD(a, b) nedělí c, je množina všech řešení prázdná.

8.10./12.10.

Připomeňme, že prvočíslem rozumíme každé přirozené číslo p > 1 splňující pro všechna přirozená a, b podmínku p = a.b ⇒ p = a nebo p = a.

1.9. Dokažte, že lze každé přirozené číslo n > 1 napsat jako součin prvočísel.

Dokážeme snadno indukcí podle n. Číslo 2 je zřejmě prvočíslo. Pokud n není prvočíslo existují taková přirozená čísla k, l < n, že n = k · l. Obě jsou samozřejmě větší než jedna a podle indukčního předpokladu máme prvočíselný rozklad čísel k = p_{1}·. . .·p_{r} a l = q_{1}·. . .·q_{s}. Tedy číslo n je součinem prvočísel p_{1}·. . .·p_{r} ·q_{1}·. . .·q_{s}. □

1.10. Dokažte, že přirozené číslo a_{n} z popisu Euklidova algoritmu je rovno právě NSD(a_{0}, a_{1}).

Indukcí podle i dokážeme rovnost NSD(a_{i}, a_{i+1} ) = NSD(a_{i−1}, a_{i}). Položme c = NSD(a_{i−1}, a_{i}) a d = NSD(a_{i}, a_{i+1} ). Protože d/a_{i} i d/a_{i+1} , d dělí i a_{i−1} = q_{i} · a_{i} + a_{i+1} , proto d ≤ c. Podobně nahlédneme, že c/a_{i} i c/a_{i−1} = q_{i} · a_{i} + a_{i+1} tedy c ≤ d a c = d. Protože a_{n}/a_{n−1}, vidíme, že a_{n} = NSD(a_{n−1}, a_{n}), a tudíž a_{n} = NSD(a_{n}, a_{n−1}) = NSD(a_{n−1}, a_{n−2}) = ⋯ = NSD(a_{0}, a_{1}). □

1.11. Definujme posloupnosti x_{i} a y_{i} tak, že x_{0} = y_{1} = 1, x_{1} = y_{0} = 0, a pro i ≥ 1 položme x_{i+1} = x_{i−1} − x_{i} · q_{i} a y_{i+1} = y_{i−1} − y_{i} · q_{i}, kde a_{i−1} = a_{i} · q_{i} + a_{i+1} . Dokažte, že a_{i} = x_{i} · a_{0} + y_{i} · a_{1}, a proto x_{n} · a_{0} + y_{n} · a_{1} je NSD(a_{0}, a_{1}).

Ověříme indukcí podle i. Zřejmě tvrzení platí pro i = 0 a i = 1.

Předpokládejme, že tvrzení platí pro i a i − 1, tedy a_{i} = x_{i} · a_{0} + y_{i} · a_{1} a a_{i−1} = x_{i−1} · a_{0} + y_{i−1} · a_{1}, a dokážeme ho pro i + 1. Dosadíme za a_{i} a a_{i−1} do vztahu

a_{i+1} = a_{i−1} − a_{i} · q_{i} = (x_{i−1} · a_{0} + y_{i−1} · a_{1}) − (x_{i} · a_{0} + y_{i} · a_{1}) · q_{i} =
= (x_{i−1} − x_{i} · q_{i}) · a_{0} + (y_{i−1} − y_{i} · q_{i}) · a_{1} = x_{i+1} · a_{0} + y_{i+1} · a_{1},

čímž jsme dokončili důkaz. □

1.12. Ověřte , že přirozené číslo p je prvočíslem právě tehdy, platí-li pro všechna přirozená a, b implikace p/a · b ⇒ p/a nebo p/b.

Nejprve předpokládejme, že p je prvočíslo a zvolíme libovolná přirozená a, b, pro něž p/a · b. Protože NSD(p, a) = 1 (p má pouze dělitele 1 a p), existují díky úvaze Příkladu 1.10 a 1.11 taková celá x a y, že 1 = a · x + p · y. Proto b = abx + pby. Protože p dělí abx i pby, platí, že p/b.

Naopak, nechť pro přirozené číslo p a všechna přirozená a, b platí, že p/a · b ⇒ p/a nebo p/b, a položme p = a · b. Potom a/p i b/p, tedy a ≤ p a b ≤ p a navíc p = a · b/a · b. Využijeme-li náš předpoklad, pak buď p/a, proto p ≤ a a následně p = a nebo p/b, a tudíž p = b, čímž jsme dokázali obrácenou implikaci dokazované ekvivalence. □

1.13. Dokažte pro každé prvočísl p a pro všechna přirozená a_{1}, a_{2}, …, a_{k} platí implikace p/a_{1}a_{2} … a_{k} ⇒ existuje takové i, že p/a_{i}.

Indukční rozšíření předchozího pozorování. □

1.14. Dokažte, že je prvočíselný rozklad přirozeného čísla určen jednoznačně až na pořadí prvočísel.

Dokážeme tvrzení pro přirozené číslo n indukcí podle n. Je-li n prvočíslo (speciálně n = 2), je prvočíselný rozklad zřejmě určen jednoznačně. Platí-li tvrzení pro všechna k < n a n = p_{1} · . . . · p_{r} = q_{1} · . . . · p_{s} jsou dva prvočíselné rozklady, potom podle tvrzení 1.13 existuje takové j, že p_{1}/q_{j}. Bez újmy na obecnosti můžeme předpokládat, že j = 1. Protože p_{1} i q_{1} jsou prvočísla, máme p_{1} = q_{1}. Nyní stačí použít indukční předpoklad pro p_{2} · . . . · p_{r} = q_{2} · . . . · p_{s} < n. □

15.10./19.10.

2. Monoidy

Připomeňme, že prvek s monoidu (S, ·, 1) je (oboustranně) invertibilní, existujeli takový prvek s^{−1} ∈ S, že s^{−1} · s = s · s^{−1} = 1. Prvek s^{−1} nazveme inverzním prvkem prvku s.

2.1. Dokažte, že množina všech invertibilních prvků monidu (G, ·, 1) tvoří jeho podmonoid.

Vezmeme-li prvky g_{1} a g_{2} z G^{∗}, platí, že existují prvky h_{1}, h_{2} ∈ G, pro něž g_{i}h_{i} = h_{i}g_{i} = 1, kde i = 1, 2. Tedy (g_{1}g_{2})(h_{2}h_{1}) = g_{1}(g_{2}h_{2})h_{1} = g_{1}1h_{1} = g_{1}h_{1} = 1 a symetricky (h_{2}h_{1})(g_{1}g_{2}) = 1. Zřejmě 1 · 1 = 1, proto G^{∗} obsahuje prvek 1. Tedy G^{∗} je podmonoid monidu (G, ·, 1). □

2.2. Nechť (G, ·, 1) je monoid a G^{∗} podmonoid všech jeho invertibilních prvků. Označme ·_{G^{∗}} restrikci operace · na množinu G^{∗} × G^{∗} a definujeme unární operaci −1 tak, že a^{−1} je právě inverzní prvek pro každé a ∈ G^{∗}. Ověřte, že (G^{∗}, ·_{G^{∗}},^{−1} , 1) je grupa.

V úloze 2.1 jsme dokázali, že G^{∗} je podmonoidem monoidu G(·, 1). Vezmemeli operaci omezenou na tento podmonoid ·|_{G^{∗}×G^{∗}}, je (G^{∗}, ·_{G^{∗}}, 1) monoid. Protože víme, že inverzní prvek je díky asociativitě operace určen jednoznačně a množina G^{∗} je na operaci inverzního prvku uzavřena, (G^{∗}, ·_{G^{∗}},^{−1} , 1) splňuje všechny axiomy grupy. □

2.3. Uvažujme monoid (Z_{n}, ·, 1) s operací · definovanou jako násobení modulo n. Označme Z_{n}^{∗} množinu všech invertibilních prvků tohoto momoidu. Dokažte, že Z_{n}^{∗} = {k ∈ Z_{n}| NSD(k, n) = 1}.

Stačí si uvědomit, že k ∈ Z_{n} je invertibilní právě tehdy, když existuje m takové, že (k · m)mod n = 1. Jestliže NSD(k, n) = 1, umíme pomocí Euklidova algoritmu najít x ∈ Z_{n} a celé y, aby kx + ny = 1, tedy hledané m = (x)mod n. Naopak, jestliže NSD(k, n) = c > 1, pak pro libovolné m je buď (km)mod n = 0 nebo c/(km)mod n. Tím jsme ověřili, že Z_{n}^{∗} = {k < n| NSD(k, n) = 1}. □

2.4. Nechť p je prvočíslo a k přirozené číslo. Určete počet invertibilních prvků monidu (Z_{p^{k}}, ·, 1).

Číslo menší než p^{k} je soudělné s p^{k}, právě když je násobkem čísla p. Nezáporných násobků čísla p menších než p^{k} je zřejmě právě p^{k−1}. To znamená, že naopak čísel nesoudělných s p^{k} máme |Z_{p^{k}}^{∗}| = |Z_{p^{k}}| − p^{k−1} = p^{k} − p^{k−1} = (p − 1)p^{k−1}. □

Zobrazení φ : N → N dané předpisem φ(n) = |{k < n| k ∈ N, NSD(k, n) = 1}| nazveme Eulerovou funkcí.

2.5. Ověřte, že φ(n) udává počet invertibilních prvků monidu (Z_{n}, ·, 1).

Tvrzení plyne okamžitě z úlohy 2.3 a definice Eulerovy funkce. □

Uvažujme monoidy (M_{j}, ·, 1) pro j = 1, …, k a definujme na kartézském součinu (∏_{j=1}^{k} M_{i}, ·, (1, …, 1)) po složkách operaci ⊙, tj.

(m_{1}, …, m_{k}) ⊙ (n_{1}, …, n_{k}) = (m_{1} · n_{1}, …, m_{k} · n_{k}).

2.6. Ověřte, že M = (∏_{j=1}^{k} M_{i}, ·, (1, …, 1)) je opět monoid a že prvek (m_{1}, …, m_{k}) monoidu M je invertibilní, právě když jsou všechny prvky m_{j}, j = 1, …, k invertibilní.

Vezměme (m_{1}, …, m_{k}), (n_{1}, …, n_{k}), (r_{1}, …, r_{k}) ∈ M. Pak

(m_{1}, …, m_{k}) ⊙ ((n_{1}, …, n_{k}) ⊙ (r_{1}, …, r_{k})) = (m_{1}, …, m_{k}) ⊙ (n_{1} · r_{1}, …, n_{k} · r_{k}) =

= (m_{1} · (n_{1} · r_{1}), …, m_{k} · (n_{k} · r_{k})) = ((m_{1} · n_{1}) · r_{1}, …, (m_{k} · n_{k}) · r_{k}) =

= (m_{1} · n_{1}, …, m_{k} · n_{k}) ⊙ (r_{1}, …, r_{k}) = ((m_{1}, …, m_{k}) ⊙ (n_{1}, …, n_{k})) ⊙ (r_{1}, …, r_{k}) a

(m_{1}, …, m_{k}) ⊙ (1, …, 1) = (m_{1}, …, m_{k}) = (1, …, 1) ⊙ (m_{1}, …, m_{k}),

čímž jsme ověřili, že je M monoid. Nyní stačí uvážit, kdy existuje prvek (r_{1}, …, r_{k}), pro který

(m_{1}, m_{2}, …, m_{k}) ⊙ (r_{1}, r_{2}, …, r_{k}) = (m_{1} · r_{1}, m_{2} · r_{2}, …, m_{k} · r_{k}) = (1, 1, …, 1)

a

(r_{1}, r_{2}, …, r_{k}) ⊙ (m_{1}, m_{2}, …, m_{k}) = (r_{1} · m_{1}, r_{2} · m_{2}, …, r_{k} · m_{k}) = (1, 1, …, 1).

□

2.7 (Čínská věta o zbytcích). Nechť n_{1}, n_{2}, …, n_{k} jsou po dvou nesoudělná kladná celá čísla a n = n_{1} ·n_{2} ·· · ··n_{k}, Dokažte, že zobrazení f : Z_{n} → ∏_{i=1}^{k} Z_{n_{i}} dané předpisem f(x) = (x modn_{1}, x modn_{2}, …, x modn_{k}) je izomorfismus grup (Z_{n}, +, −, 0) a (∏_{i=1}^{k} Z_{n_{i}}, +, −, 0) a monoidů (Z_{n}, ·, 1) a (∏_{i=1}^{k} Z_{n_{i}}, ·, 1).

Přímo z definice snadno vidíme, že je f zobrazení slučitelné se všemi operacemi. Zbývá nahlédnout, že jde o bijekci. Protože jsou Z_{n} a ∏_{i=1}^{k} Z_{n_{i}} stejně velké konečné množiny, stačí nahlédnout, že je f prosté. Nechť pro a ≤ b ∈ Z_{n} platí, že f(a) = f(b). Potom f(b − a) = 0, tedy n_{i}/b − a pro všechna i = 1, …, k. Protože jsou n_{i} po dvou nesoudělná a 0 ≤ b − a ≤ n − 1, máme i n/b − a, tudíž b = a. □

22.10./26.10.

2.8. Uvažujme zobrazení f : Z_{45} → Z_{5} × Z_{9} z 2.7, tj.f(a) = (a mod5, a mod9). Určete (jednoznačně určené) a ∈ Z_{45}, pro které f(a) = (3, 2).

Hledáme a ∈ Z_{45} pro něž existují taková x ∈ Z_{9} a y ∈ Z_{5}, že 5x + 3 = a a 9y + 2 = a, tedy musí platit 5x + 3 = 9y + 2. Upravíme-li rovnici na tvar 9y − 5x = 1, řešíme obvyklou úlohu. Snadno zjistíme, že 9 · 4 − 5 · 7 = 1, tedy a = 5 · 7 + 3 = 9 · 4 + 3 = 38. □

2.9. Uvažujme zobrazení f : Z_{720} → Z_{5} × Z_{9} × Z_{16} z 2.7. Najděte b ∈ Z_{720}, pro které f(b) = (3, 2, 13).

Definujme zobrazení g : Z_{45} × Z_{16} → Z_{5} × Z_{9} × Z_{16} předpisem g(u, v) = (umod5, umod9, v) a zobrazení h : Z_{720} → Z_{45} × Z_{16} z Čínské věty o zbytcích, tj. h(w) = (w mod45, w mod16). Všimněme si, že f = gh, navíc jsou obě zobrazení g a h bijekce a f^{−1}(3, 2, 13) = h^{−1}(g^{−1}(3, 2, 13)). Protože je zobrazení g součinem bijekce z 2.7 a identity a vzor dvojice (3, 2) už jsme spočítali v předchozí úloze, vidíme, že g^{−1}(3, 2, 13) = (38, 13). Zbývá nám tedy stejnou úvahou jako v předchozím příkladu najít vzor h^{−1}(38, 13), tj. vyřešit rovnice 45x + 38 = b a 16y + 13 = b pomocí diofantické rovnice 16y − 45x+ = 25. Obvyklým způsobem zjistíme například, že 5 · 45 − 14 · 16 = 1, proto 25 = 125 · 45 − 350 · 16 = 10 · 16 − 3 · 45. Tedy b = 45 · 3 + 38 = 16 · 10 + 13 = 173. □

2.10. Buď p_{1} < p_{2} < ⋯ < p_{k} prvočísla a r_{1}, r_{2}, …, r_{k} kladná celá čísla. Dokažte, že φ(∏_{i=1}^{k} p_{i}^{r_{i}}) = ∏_{i=1}^{k} φ(p_{i}^{r_{i}}) = ∏_{i=1}^{k} (p_{i} − 1)p_{i}^{r_{i}−1}.

Položme pro přehlednost n_{i} = p_{i}^{r_{i}} a n = ∏_{i=1}^{k} n_{i}. Protože čísla n_{i} a n_{j} jsou pro všechna i ≠ j nesoudělná, můžeme využít úlohu 2.7, podle níž jsou monoidy (Z_{n}, ·, 1) a (∏_{i=1}^{k} Z_{n_{i}}, ·, (1, …, 1) izomorfní, proto mají stejné počty invertibilních prvků. Použijeme-li dále 2.6 dostáváme: φ(n) = |(Z_{n}^{∗}| = | ∏_{i=1}^{k} Z_{n_{i}}^{∗}| = ∏_{i=1}^{k} |Z_{n_{i}}^{∗}| = ∏_{i=1}^{k} φ(n_{i}) = ∏_{i=1}^{k} φ(p_{i}^{r_{i}}). Konečně poslední rovnost dostáváme z úloh 2.4 a 2.5.

□

2.11. Určete počet invertibilních prvků monoidu (Z_{1352} , ·, 1).

Podle 2.3 potřebujeme určit hodnotu φ(1352) Eulerovy funkce na prvku 1352. Prvočíselný rozklad čísla 1352 je 2^{3} ·13^{2} a z 2.10 dostáváme, že |Z_{1352}^{∗} | = φ(1352) = (13 − 1) · 13^{1} · (2 − 1) · 2^{2} = 624. □

2.12. Rozhodněte, zda jsou izomorfní monoidy (Z_{4}, +, 0) a (Z_{8}^{∗}, ·, 1).

Stačí si rozmyslet, že pro všechny prvky a ze Z_{8}^{∗} = {1, 3, 5, 7} platí a · a = 1. V monoidu (Z_{4}, +, 0) máme 3 + 3 = 2, což je různé od neutrálního prvku 0, tedy monoidy nejsou izomorfní. □

2.13. Rozhodněte, zda jsou izomorfní monoidy (Z_{2} × Z_{2}, +, 0) a (Z_{8}^{∗}, ·, 1).

Sestrojíme-li bijekci g : Z_{2} × Z_{2} → Z_{8}^{∗} výčtem g((0, 0)) = 1, g((0, 1)) = 3, g((1, 0)) = 5 a g((1, 1)) = 7, snadno ověříme, že se jedná o homomorfismus, tedy dané monoidy jsou izomorfní. □

2.11./5.11.

3. Grupy

3.1. Nechť p a s jsou permutace z grupy S_{n} a nechť p(a) = b, kde a, b ∈ {1, …, n}. Dokažte, že [sps^{−1}](s(a)) = s(b).

Důkaz tvrzení je zcela přímočarý. Důležitým důsledkem je ovšem pozorování, že permutace p a sps^{−1} mají stejný počet stejných cyklů, neboť jsme právě dokázali, že

s ∘ [… (… ab …) …] ∘ s^{−1} = … (… s(a)s(b) …) ….
□

3.2. Mějme p = (1346)(27)(589) a q = (16)(29)(345) dvě permutace z grupy S_{9}. Spočítejte hodnoty pqp^{−1} a qpq^{−1}.

Postupujeme podle předchozího pozorování:

[(1346)(27)(589)] ∘ [(16)(29)(345)] ∘ [(1346)(27)(589)]^{−1} = (31)(75)(468)

a

[(16)(29)(345)] ∘ [(1346)(27)(589)] ∘ [(16)(29)(345)]^{−1} = (6451)(97)(382).

□

3.3. Mějme permutace p_{1} = (126)(37)(458) a p_{2} = (12)(345)(678) z grupy S_{8}. Rozhodněte, zda jsou permutace p_{1} a p_{2} konjugované, tj. zda existuje permutace q ∈ S_{8} s vlastností qp_{1}q^{−1} = p_{2} a případně takovou permutaci q najděte.

Využijeme opačný postup k postupu v předchozím příkladu. Obě permutace jsou stejného typu (což je zřejmě nutná podmínka, aby permutace q existovala). Seřaďme stejnými n-cykly pod sebe, například:

{(126)(37)(458) \atop (345)(12)(678)}

Zřejmě potom permutace q = (13)(24657)(8) splňuje podmínku qp_{1}q^{−1} = p_{2}. □

3.4. Ověřte, že alternující grupa na čtyřech prvcích A_{4} neobsahuje žádnou podgrupu řádu 6.

Uvědomme si, že A_{4} = {Id, (12)(34), (13)(24), (14)(23), (123), (132), (124), (142), (134), (143), (234), (243)}. Předpoládejme, že máme podgrupu H řádu alespoň 6. To určitě znamená, že H obsahuje alespoň dva trojcykly, tj. permutace tvaru (abc), bez újmy na obecnosti můžeme předpokládat, že A_{4} obsahuje trojcyklus (123). Podle Lagrangeovy věty je index podgrupy H v grupě A_{4} nejvýše 2. Využijeme-li Příkladu 1.37(1) a (2) z přednášky, vidíme, že jak podgrupa indexu 1, tak podgrupa indexu 2 je normální, proto je H normální podgrupa A_{4}. To ovšem znamená, že p(123)p^{−1} = (p(1)p(2)p(3)) ∈ H pro každé p ∈ A_{4}. Nyní snadno spočítáme, že

(214) = (12)(34) ∘ (123) ∘ ((12)(34))^{−1},
(341) = (13)(24) ∘ (123) ∘ ((13)(24))^{−1},
(432) = (14)(23) ∘ (123) ∘ ((14)(23))^{−1}.

Protože je H normální podgrupa, leží (214), (341) i (432) v H, navíc v H leží i inverzní permutace (124), (143) a (243), tedy H obsahuje více než 6 prvků. Z Lagrangeovy věty už plyne, že |H| = 12, proto H = A_{4}. □

3.5. Ověřte, že pro každý prvek g konečné grupy G platí, že g^{|G|} = 1.

Z Poznámky 1.32 okamžitě plyne, že g^{|⟨g⟩|} = 1. Nyní stčí použít Lagrangeovu větu a pozorování, že (g^{a})^{b} = g^{ab} pro všechna a, b ∈ N. Proto g^{|G|} = (g^{|⟨g⟩|})^{\frac{|G|}{|⟨g⟩|}} = 1^{\frac{|G|}{|⟨g⟩|}} = 1. □

3.6. [Malá Fermatova věta] Dokažte, že pro každé a nesoudělné s n platí, že (a^{φ(n)})modn = 1.

Stačí vzít jako grupu G z předchozího příkladu grupu invertibillních prvků monoidu (Z_{n}, ·, 1) tj. prvků nesoudělných s n. □

Připomeňme, že (G, ·,^{−1} , 1) je cyklická grupa, existuje-li její prvek g, pro nějž ⟨g⟩ = G, tj. jednoprvková množina {g} generuje celou nosnou množinu grupy. Všimněme si, že ⟨g⟩ = {g^{n}| n ∈ Z}, kde g^{0} = 1, g^{n} = g · g^{n−1} pro n > 0 a g^{n} = (g^{−1})^{|n|} pro n < 0.

9.11./12.11.

3.7. Spočítejte (53^{65})mod120.

Díky Malé Fermatově větě víme, že (53^{φ(120)} )mod120 = (53^{32})mod120 = 1. Tedy(53^{65})mod120 = (((53^{32})^{2})mod120 · 53)mod120 = 1 · 53 = 53. □

3.8. Nechť (G, ·,^{−1} , 1) je grupa, H její podgrupa řádu 70 a K její podgrupa řádu 16. Určete počet prvků G, vite-li, že |G| < 1000, a rozhodněte, zda je průnik H ∩ K nutně komutativní grupa.

Podle Lagrangeovy věty musí řád podgrup H i K dělit |G|, proto 70/|G| a 16/|G| a tudíž 560 = nsn(70, 16)/|G|. Protože |G| < 1000, máme |G| = 560.

Zabývejme se nyní grupou H ∩ K. Opět použijeme Lagrangeovu větu, tentokrát pro H ∩ K jako podgrupu grupy H i K. Velikost průniku H ∩ K, proto musí dělit řád obou grup H i K, tedy |H ∩ K|/NSD(70, 16) = 2. Proto je průnik H ∩ K jednoprvková nebo dvouprvková, tedy v obou případech komutativní grupa. □

3.9. Najděte nějakou grupu, která by měla 560 prvků a obsahovala podgrupy řádu 70 a 16.

Stačí, abychom vzali grupu (Z_{560}, +, −, 0). Její podgrupou řádu 70 je cyklická grupa ⟨8⟩ a podgrupou řádu 16 cyklická grupa ⟨35⟩. □

3.10. Popište množinu generátorů cyklické grupy (Z_{n}, +, −, 0).

Uvědomme si, že číslo k je generátorem právě tehdy, když podgrupa ⟨k⟩ obsahuje prvek 1 a to nastává právě tehdy, když je NSD(k, n) = 1. Vidíme, že množinu generátorů cyklické grupy (Z_{n}, +, −, 0) tvoří právě invertibilní prvky monoidu (Z_{n}, ·, 1). □

3.11. Určete počet generátorů cyklické grupy (Z_{50}, +, −, 0).

Podle úvahy z 3.10 a popisu množiny invertibilních prvků monoidu (Z_{n}, ·, 1) úlohy 2.10 potřebujeme určit hodnotu Eulerovy funkce na prvku 50. Prvočíselný rozklad čísla 50 je 5^{2} · 2, proto φ(50) = (5 − 1) · 5^{1} · (2 − 1) = 20. □

3.12. Určete počet generátorů cyklické grupy řádu 81.

Uvážíme-li, že cyklická grupa řádu 81 je izomorfní grupě (Z_{81}, +, −, 0), postujpujeme stejně jako v předchozím příkladu: prvočíelný rozklad čísla 81 je 3^{4}, tedy počet generátorů cyklické grupy řádu 81 je φ(81) = (3 − 1) · 3^{3} = 54. □

3.13. Nechť G je konečná cyklická grupa, |G| = n, a nechť k dělí n. Ukažte, že existuje právě jedna podgrupa grupy G, která má k prvků.

K důkazu využijeme charakterizace cyklických grup (Důsledek 1.47 z přednášky), díky němuž stačí tvrzení dokázat pro (izomorfní) grupu (Z_{n}, +, −, 0). Jestliže k = 1, je tvrzení triviální, předpokládejme tedy, že k > 1, a položme a = \frac{n}{k}. Potom snadno nahlédneme, že ⟨a⟩ = {0, a, 2a, …, (k − 1)a}, tudíž |⟨a⟩| = k. Mějme nyní nějakou podgrupu H řádu k grupy Z_{n}. Podle Lagrangeovy věty (Věta 1.29 z přednášky) řád grupy ⟨h⟩ dělí k pro každý prvek h ∈ H, proto (k·h)modn = 0. Tudíž k·h = c·n pro vhodné celé číslo c, tedy h = \frac{c·n}{k} = c·a. Tím jsme ověřili, že H je částí podgrupy ⟨a⟩. Protože se ovšem jedná o dvě konečné stejně velké množiny dostáváme, že H = ⟨a⟩, čímž jsme ověřili jednoznačnost volby. □

3.14. Kolik podgrup obsahuje cyklická grupa řádu 98?

Využijeme úvahu úlohy 3.13: každému děliteli řádu cyklické grupy odpovídá právě jedna její podgrupa. Potřebujeme tedy jen spočítat dělitele čísla 98, kterých je 6 (tj. 1, 2, 7, 14, 49, 98). □

16.11./19.11.

Zvolme pro následující úvahy p a q dvě různá lichá prvočísla a položme m = nsn(p − 1, q − 1).

3.15. Dokažte, že pro každé nezáporné celé číslo x platí rovnosti (x^{m+1} )modp = (x)modp a (x^{m+1} )modq = (x)modq.

Tvrzení samozřejmě stačí dokázat jen pro prvočíslo p.

Předně zvolme x a uvědomme si, že x = x_{0} + p · α pro vhodné x_{0} ∈ Z_{p} a α celé nezáporné, což znamená, že x_{0} = (x)modp. Proto

(x^{m+1} )modp = (x_{0}^{m+1} + p · (…))modp = (x_{0}^{m+1} )modp.

Z 3.6 dostáváme, že (x_{0}^{m+1} )modp = x_{0} pro nenulové x_{0} a pro x_{0} = 0 je tvrzení triviální. Tedy (x^{m+1} )modp = x_{0} = (x)modp. □

3.16. Dokažte, že pro každé x ∈ Z_{pq} platí rovnosti (x^{m+1} )modpq = x.

Tentokrát využijeme 2.7 pro (bijekci) f : Z_{pq} → Z_{p}×Z_{q}. Protože podle předchozí úlohy máme f(x^{m+1} ) = f(x) jsou v monoidu (Z_{pq}, ·, 1) hodnoty x^{m+1} a x stejné, což je právě tvrzení, jež jsme měli dokázat. □

3.17 (Rivest, Shamir, Adleman). Zvolme e < m nesoudělné s m a pak (například pomocí Euklidova algoritmu) najdeme takové d < m, že (ed)modm = 1. Nyní pro každé a ∈ Z_{pq} platí, že (a^{e})^{d} = a^{ed} = a^{um+1} = a (počítáno v Z_{pq}, tedy modulo pq).

Pomocí vlastnosti čísel p, q, m, d, e můžeme nyní popsat protokol asymetrického šifrování známý pod zkratkou RSA. Položíme-li n = p · q, je veřejným klíčem je dvojice čísel (pq, e) a soukromý klíč tvoří tajný exponent d. Chceme-li informaci vyjádřenou posloupností hodnot a_{1}, …, a_{k} ∈ Z_{pq} adresovat majiteli soukromého klíče, stačí ji zašifrovat pomocí mocnění veřejně známou hodnotou e v monoidu Z_{pq}(·, 1), tj. odeslat zprávu (a_{1}^{e})modpq, …, (a_{k}^{e})modpq. K jejímu rozluštění stačí umocnit v Z_{pq}(·, 1) pomocí tajného exponentu, protože (a_{i}^{e})^{d} = a_{i}^{ed} = a_{i}. Naopak, zveřejnění-li majitel soukromého klíče zašifrovanou zprávu (a_{1}^{d})mod pq, …, (a_{k}^{d})mod pq, mohou si příjemci zprávy stejným způsobem (tj. umocněním na veřejně známý exponent e: ((a_{1}^{d})^{e})mod pq, …, ((a_{k}^{d})^{e})mod pq = a_{1}, …, a_{k}) ověřit, že odesilatel zprávy opravdu zná tajný exponent.

Poznamenejme, že je ze znalosti n a e obtížné najít d (odpovídá to nalezení prvočíselného rozkladu čísla n, což je úloha, pro níž není znám algoritmus polynomiální složitosti), zatímco mocnění čísel v Z_{pq} je (i pro velké exponenty a velké pq) velmi snadné a rychlé.

Další úlohy

(1) Najděte všechna celočíselná řešení rovnice 324 · x + 88 · y = c postupně pro c = 0, 2, 88, −4, −88.

(2) Najděte všechna celočíselná řešení rovnice 15 · x − 44 · y = c postupně pro c = 1, 2, −2.

(3) Najděte (všechna) celočíselná řešení rovnice 15 · x + 18 · y + 10 · z = 1.

(4) Spočítejte v tělese Z_{83} hodnoty 15^{−1} a (3^{−1} + 6 · 53^{−1})^{−1}.

(5) Vyřešte v tělese Z_{97} rovnici 7^{−1} · x = 51^{−1}.

(6) Ověřte, že algoritmus popsaný v Pozorování 1.8 pracuje správně.

(7) Dokažte pro všechna kladná celá čísla a, b platí, že nsn(a, b) = \frac{a·b}{NSD(a,b)} .

(8) Najděte a ∈ Z_{315}, o kterém víte, že (a)mod5 = 3, (a)mod7 = 4, (a)mod9 = 5.

(9) Najděte a ∈ Z_{2520} , o kterém víte, že (a)mod8 = 1 (a)mod5 = 3, (a)mod7 = 4, (a)mod9 = 5.

(10) Najděte a ∈ Z_{630}, o kterém víte, že (a)mod2 = 1 (a)mod5 = 3, (a)mod7 = 4, (a)mod9 = 5.

(11) Rozhodněte, zda existuje a ∈ Z_{999} splňující podmínku, že (a)mod9 = 5 (a)mod3 = 2, (a)mod11 = 4.

(12) Rozhodněte, zda existuje a ∈ Z_{999} splňující podmínku, že (a)mod9 = 5 (a)mod3 = 2, (a)mod37 = 4.

(13) Popište obor hodnot zobrazení β : Z_{300} → Z_{20} × Z_{15} daného předpisem β(a) = ((a)mod20, (a)mod15).

(14) Rozhodněte, zda jsou izomorfní grupy (Z_{4}, +, −, 0) a (Z_{2} × Z_{2}, +, −, 0).

(15) Rozhodněte, zda jsou izomorfní grupy (Z_{6}, +, −, 0) a (Z_{2} × Z_{3}, +, −, 0).

(16) Rozhodněte, zda jsou izomorfní grupy (S_{3}, ∘,^{−1} , Id) a (Z_{2} × Z_{3}, +, −, 0).

(17) Rozhodněte, zda je grupa (Z_{20} × Z_{30}, +, −, 0) cyklická.

(18) Rozhodněte, zda je grupa (Z_{21} × Z_{31}, +, −, 0) cyklická.

(19) Rozhodněte, zda jsou permutace p_{1} a p_{2} konjugované v S_{9}, jestliže a) p_{1} = (13)(259) a p_{2} = (247)(58),

b) p_{1} = (13)(259) a p_{2} = (13)(259)(48)

(20) Rozhodněte, zda jsou permutace (13)(259) a (247)(58) konjugované v A_{9}.

(21) Dokažte, že pro každé přirozené n existuje nekonečně neizomorfních konečných grup obsahujících právě n podgrup.