Masarykova Univerzita v Brně Přírodovědecká fakulta
GRUPY – SBÍRKA PŘÍKLADŮ bakalářská práce
Brno 2005
Vít Musil
i
Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně s použitím uvedené literatury. v Brně, 21. srpna 2005
................. Vít Musil
i
Obsah Úvod Grupy 1 2 3 4 5 6 7 8 9 10
1
Pojem grupy . . . . . . . . Permutace . . . . . . . . . . Grupy zbytkových tříd . . . Základní vlastnosti grup . . Podgrupy . . . . . . . . . . Izomorfismy a součiny grup Lagrangeova věta . . . . . . Homomorfismy grup . . . . Faktorové grupy . . . . . . Konečné grupy . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
2 2 6 10 15 19 23 26 29 32 37
Výsledky příkladů
39
Literatura
45
ii
Úvod Tento materiál by měl sloužit jako pomůcka k praktickému procvičení látky probírané v první části (Grupy) skript Jíří Rosický, Algebra. Pro přehlednost jsou proto jednotlivé kapitoly pojmenovány a značeny zcela totožně. Na úvod každé z nich jsou shrnuty nejdůležitější fakta z teorie, jako věty, definice a podobně, které pomohou při řešení některých příkladů. V části označené jako TEST jsou shromážděny otázky na něž se odpovídá pouze ano nebo ne, otázky jsou formulovány tak, že vyžadují pozorné přečtení. Pak následuje několik příkladů s podrobně rozepsaným řešením, na něž navazují příklady bez řešení, jejichž výsledky jsou na konci celé publikace. Příklady jsem čerpal z těch, které jsme řešili na cvičení, ze starších písemek prof. RNDr. R. Kučery, CSc. a ze sbírky Mgr. O. Klímy, PhD., jenž je vedoucím mé bakalářské práce a jemuž bych chtěl poděkovat za cenné připomínky při psaní.
1
Grupy 1
Pojem grupy
Definice 1.1: Množina G spolu s operací · se nazývá grupoid. Označujeme jej symbolem (G, ·). Grupoid nazveme komutativní, resp. asociativní, jestliže je operace · komutativní, resp. asociativní. Asociativní grupoid se též nazývá pologrupa. [1, Definice 1.4 strana 7] Definice 1.2: Prvek e ∈ G se nazývá jednotkovým prvkem nebo též neutrálním prvkem grupoidu G, jestliže e·a=a·e=a pro libovolné a ∈ G. [1, Definice 1.5 strana 8] Věta 1.3:
Grupoid má nejvýše jeden jednotkový prvek. [1, Věta 1.6 strana 8]
Definice 1.4: Buď G grupoid s jednotkovým prvkem e a nechť a ∈ G. Prvek b ∈ G se nazývá inverzní k prvku a, jestliže a · b = b · a = e. [1, Definice 1.7 strana 8] Věta 1.5: Buď G pologrupa s jednotkovým prvkem, a ∈ G. Pak existuje nejvýše jeden prvek v G inverzní k a. [1, Věta 1.8 strana 8] Definice 1.6: Grupoid G se nazývá grupa, jestliže je asociativní, má jednotkový prvek a k libovolnému jeho prvku existuje prvek inverzní. [1, Definice 1.9 strana 8] ♣
♣
♣
♣
♣
Úloha i: Je dán grupoid (R, ◦), zjistěte jestli je asociativní, přitom x ◦ y = (x + y) · (1 + xy).
Řešení: (x◦y)◦z = (x+y)·(1+xy) ◦z = (x+y)·(1+xy)+z · 1+ (x+y)·(1+xy) ·z 2
1. POJEM GRUPY
3
x◦(y◦z) = x◦ (y+z)·(1+yz) = x+(y+z)·(1+yz) · 1+x· (y+z)·(1+yz) Pokud dosadíme například za x = −1, y = 1, z = 2, pak dostaneme dva různé (2 a -64) výsledky. Grupoid tedy není asociativní. Úloha ii: Rozhodněte, zda je grupoid (G, ◦) grupa, kde G = Q∗ a pro libovolná x, y ∈ G platí x ◦ y = |x · y| Řešení: • Je to pologrupa? ANO Nechť x, y, z ∈ G pak x ◦ (y ◦ z) = x ◦ |y · z| = |x · y · z| (x ◦ y) ◦ z = |x · y| ◦ y = |x · y · z| • Neutrální prvek n? NE Musíme najít takový prvek e ∈ G, že pro libovolné x ∈ G platí e ◦ x = =x◦e=x Mějme například x = −3, pak −3 ◦ e = | − 3 · e| by se mělo rovnat −3, hned vidíme, že takové e neexistuje. Tedy (G, ◦) není grupa. Úloha iii: Rozhodněte, zda je (M2 (Z), +) grupa, popřípadě jestli je tato grupa komutativní. (Symbol M2 (Z) značí množinu všech matic typu 2/2, jejíž prvky jsou z množiny Z.) Řešení: • Jedná se o grupoid? ANO, protože + je operací na množině (M2 (Z), +). • Jedná se o pologrupu? ANO, protože + je asociativní. 0 0 • Existuje neutrální prvek? ANO, je jím matice . 0 0 a b • Má každý prvek prvek inverzní? ANO, k matici je to matice c d −a −b . −c −d ♣ TEST:
♣
♣
♣
♣
Rozhodněte zda jsou následující výroky pravdivé:
1. V každé pologrupě s neutrálním prvkem ke každému prvku existuje nejvýše jeden prvek inverzní. 2. V každém grupoidu s neutrálním prvkem existuje ke každému prvku nejvýše jeden prvek inverzní. 3. Každý grupoid má právě jeden neutrální prvek ♣
♣
♣
3
♣
♣
1. POJEM GRUPY
4
Příklad 1.1: Je dána množina G a operace ◦ na této množině. Rozhodněte, je-li (G, ◦) grupoid. a) G = N a pro libovolné x, y ∈ G platí x ◦ y = x − y, b) G = {−1, 0, 1} a pro libovolné x, y ∈ G platí x ◦ y = x · y, c) G = {−1, 0, 1} a pro libovolné x, y ∈ G platí x ◦ y = x + y, d) G = {1, 2, 3, 5, 10, 15, 20, 30} a pro libovolné x, y ∈ G platí x ◦ y = (x, y), kde (x, y), značí největší společný dělitel čísel x a y. Příklad 1.2:
Dokažte větu 1.3 a větu 1.4.
Příklad 1.3: Na množině G = {a, b, c, d} je dána operace ◦ tabulkou. Rozhodněte, zda je grupoid (G, ◦) komutativní, resp. asociativní, resp. jestli má neutrální prvek.
a)
◦ a b c d
a c c c c
b a a a a
c b b b b
d d d d d
b)
◦ a b c d
a c a b a
b a a d b
c b d b c
d a b c d
Příklad 1.4: Napište multiplikativní tabulku grupy (G, ·), kde G = {e, f, g}, když víte, že e · f = g Příklad 1.5: množině G.
Je dána množina G = {a, b, c} a částečná tabulka operace ◦ na ◦ a b c
a a · ·
b c · ·
c a b ·
Doplňte tabulku tak, aby (G, ◦) a) byl grupoid s neutrálním prvkem, b) byl grupoid v němž má každý prvek inverzi, c) byla pologrupa, d) byla grupa. Příklad 1.6: Nechť G je libovolná množina, která má alespoň dva prvky. Na G definujeme operaci ◦ takto: x ◦ y = x, pro libovloné x, y ∈ G. Zjistěte jestli (G, ◦) je grupa, resp. pologrupa, je-li tato komutativní a má neutrální prvek. Co se změní, jestliže bude množina G jednoprvková?
4
1. POJEM GRUPY
5
Příklad 1.7: Je dán komutativní grupoid (G, ◦). Rozhodněte, zda je (G, ◦) komutativní grupou. Přitom: a) G = Q+ ; ◦ je násobení čísel, b) G = Q∗ ; x ◦ y = |x · y|, c) G = {x ∈ R | x 6= 0 ∧ |x| ≤ 1}; ◦ je násobení čísel, d) G = h0, 1); x ◦ y = x + y − [x + y], e) G = {a + b · i | a, b ∈ Z}; ◦ je sčítání komplexních čísel, √ f) G = {a + 5 · b · i | a, b ∈ Q ∧ (a2 + b2 ) 6= 0}; ◦ je násobení komplexních čísel, kde Q+ značí množinu všech kladných racionálních čísel resp. [x + y] značí celou část reálného čísla x + y, tj. největší celé číslo, které nepřevyšuje číslo x + y. Příklad 1.8: Uvažme množinu M = {(a, b) | a, b ∈ R, a < 0 < b} ∪ ∅ otevřených intervalů reálných čísel. Ukažte, že průnik ∩ je operací na této množině. Rozhodněte, zda je operace ∩ asociativní a zda existuje neutrální prvek. Je (M, ∩) grupa? Příklad 1.9: Uvažme množinu N = {(a, b) | a, b ∈ R, a < 0 < b} otevřených intervalů reálných čísel. Ukažte, že sjednocení ∪ je operací na této množině. Rozhodněte, zda je operace ∪ asociativní a zda existuje neutrální prvek. Je (N, ∪) grupa? Příklad 1.10: Definujeme zobrazení fi : R − {0, 1} → R − {0, 1} pro i = 1, 2, . . . , 6 takto: f3 (x) = 1 − x f1 (x) = x f2 (x) = x1 x 1 f4 (x) = x−1 f5 (x) = x−1 f6 (x) = 1−x x Vytvořte tabulku množiny G = {f1 , f2 f3 , f4 , f5 , f6 } s operací skládání zobrazení a dokažte, že se jedná nekomutativní grupu. Příklad 1.11: Rozhodněte, zda (Q, ◦), kde x ◦ y = 2 · (x · y + x + y) + 1 pro libovolné x, y ∈ Q je grupa. Své tvrzení dokažte. Příklad 1.12: Nechť (G, ◦) je grupa a a nějaký její pevně zvolený prvek. Dokažte, že potom (G, ) je také grupa, kde operace je definována předpisem g h = g ◦ a ◦ h.
5
2. PERMUTACE
2
6
Permutace
Definice 2.1: Buď X množina. Bijektivní zobrazení množiny X na sebe nazýváme permutace množiny X. Množina všech permutací množiny X se označuje symbolem S(X). [1, Definice 2.2 strana 10] Věta 2.2: Každou neidentickou permutaci množiny {1, . . . , n} lze rozložit v součin navzájem nezávislých cyklů. Tento rozklad je určen jednoznačně, až na pořadí cyklů. [1, Věta 2.5 strana 12] Definice 2.3: Buď f permutace množiny {1, . . . , n}. Řekneme, že uspořádaná dvojice [i, j] je inverze permutace f , jestliže 1 ≤ i < j ≤ n a f (i) > f (j). Permutace f se nazývá sudá nebo lichá podle toho, zda má sudý nebo lichý počet inverzí. Parita p(f ) permutace f se definuje rovna číslu 1, pokud permutace f je sudá, a číslu −1, je-li f lichá. [1, Definice 2.7 strana 13] Věta 2.4: Součin k transpozic je sudá permutace ⇔ k je sudé číslo. [1, Věta 2.8 strana 13] Věta 2.5:
Buďte f, g permutace množiny {1,. . . ,n}. Pak p(f ◦ g) = p(f ) · p(g).
[1, Věta 2.9 strana 13] ♣
♣
♣
♣
♣
1 2 3 4 5 6 7 8 9 , zapište 5 4 1 2 3 9 7 6 8 tuto permutaci, jako složení navzájem nezávislých cyklů. Řešení: Při řešení postupujeme takto, vybereme například první prvek 1 a do cyklu za něj zapíšeme prvek, na který se zobrazuje (1, 5, ?), za něj ten, na nějž se zobrazuje (1, 5, 3, ?) a tak pořád dál. Pokud se posledně zapsaný prvek v cyklu zobrazuje na první v cyklu, cyklus uzavřeme (1, 5, 3) a složíme ho s dalším nezávislým cyklem, který utvoříme zcela analogicky z prvků, které ještě nejsou v cyklech obsaženy. Prvek, který se zobrazuje sám na sebe v takovémto zápisu neuvádíme. Celkový výsledek je tedy Úloha i: Je dána permutace f =
f = (1, 5, 3) ◦ (2, 4) ◦ (6, 9, 8) Úloha ii: Jsou dány permutace 1 2 3 4 5 a= , 2 3 1 5 4
b=
1 2 4 1
3 4 2 3
5 5
a) Zapište tyto permutace jako složení navzájem nezávislých cyklů. b) Spočtěte permutaci a ◦ b. c) Spočtěte permutaci a15 . 6
2. PERMUTACE
7
d) Rozložte permutaci b na součin transpozic. Řešení: a) Jako v předešlém příkladě: a = (1, 2, 3) ◦ (4, 5), b = (1, 4, 3, 2) b) Nejprve si permutace zapíšeme jako složení nezávislých cyklů a ty pak složíme a ◦ b = (1, 2, 3) ◦ (4, 5) ◦ (1, 4, 3, 2). Začneme od prvního cyklu (nejvíce vpravo), 1 se podle něj zobrazí na 4, podle druhého přejde 4 na 5 a poslední nechá 5 na 5 a tedy po prvním kroku máme (1, 5, ?) a pokračujeme, 5 se podle prvního nemění, podle druhého přejde na 4 a poslední nechává opět 4 na sebe samu, po druhém projití dostáváme tedy (1, 5, 4, ?) a takto pokračujeme dál. Celkově tedy dostaneme, že a ◦ b = (1, 2, 3) ◦ (4, 5) ◦ (1, 4, 3, 2) = (1, 5, 4) c) Opět si nejprve zapíšeme permutaci jako složení nezávislých cyklů. Poté můžeme každý cyklus umocňovat zvlášť, tedy: a15 = (1, 2, 3)15 ◦ (4, 5)15 . Víme, že pokud cyklus délky k umocníme na n, takové, že k | n přejde tento cyklus na identitu, pak už není těžké získat výsledek a15 = (1, 2, 3)15 ◦ (4, 5)15 = (1, 2, 3)5·3 ◦ (4, 5)7·2+1 = (4, 5).
d)Jelikož víme, že každou permutaci lze zapsat jako součin transpozic takto (i1 , . . . ik ) = (i1 , ik ) ◦ · · · ◦ (i1 , i3 ) ◦ (i1 , i2 ), pak tedy b = (1, 2) ◦ (1, 3) ◦ (1, 4). Úloha iii: Dokažte, že permutace (s8 ◦ t11 ◦ s16 ◦ t13 ) je vždy sudá. Řešení: Využijme toho, že p(an ) = p(a)n a tedy jakákoli permutace umocněná na sudé číslo je sudá. Tedy: p(s8 ) · p(t11 ) ◦ p(s16 ) ◦ p(t13 ) = 1 · p(t11 ) · 1 · p(t13 ) = p(t11 ◦ t13 ) = p(t24 ) = 1 Tím je tvrzení dokázáno. ♣ TEST:
♣
♣
♣
♣
Rozhodněte zda jsou následující výroky pravdivé:
1. Každá transpozice je lichou permutací. 2. Každou neidentickou permutaci konečné množiny lze rozložit do součinu transpozic. 3. Každá lichá permutace je transpozicí. 4. Grupa (Sn , ◦) je komutativní pro každé n ∈ N. 5. Pro každé n ∈ N, n ≥ 3 je grupa (Dn , ◦) komutativní (grupa (Dn , ◦) je grupa všech symetrií pravidelného n-úhelníka). [1, strana 14] 6. Cyklus délky 5 umocněný na 321 má lichou paritu. 7. S6 , tj. grupa všech permutací na šesti prvcích, má 36 prvků. ♣
♣
♣
7
♣
♣
2. PERMUTACE Příklad 2.1:
8
Jsou dány permutace f ,g,h ∈ S9 předpisem 1 2 3 4 5 6 7 8 9 f= , 9 3 7 8 1 4 2 6 5 1 2 3 4 5 6 7 8 9 g= , h = f ◦ g. 8 1 5 2 6 3 7 4 9
a) Napište permutace f , g a h jako složení navzájem nezávislých cyklů. b) Určete paritu permutací f , g a h. c) Spočtěte permutaci f 100 ◦ g 100 a napište ji jako součin navzájem nezávislých cyklů. Příklad 2.2:
Jsou dány permutace u,v,w ∈ S9 předpisem 1 2 3 4 5 6 7 8 9 u= , 3 4 7 2 1 9 8 6 5
v=
w=
1 5
2 2
3 1
1 8
2 3 1 4
4 4
5 3
6 8
4 5 6 3
7 7
6 7 7 5
9 9
8 9 9 2
8 6
,
,
a) Zapište permutace u, v, w jako složení nezávislých cyklů. b) Spočtěte permutace u ◦ v, v ◦ u, w ◦ v. c) Spočtěte permutace w ◦ v ◦ u, w ◦ v ◦ w, v ◦ w ◦ u. d) Spočtěte permutaci v 103 . e) Spočtěte permutaci w27 . f) Spočtěte permutaci u120 ◦ v −3 . g) Zapište permutaci v 32 ◦ w32 jako součin transpozic a určete její paritu. h) Zapište permutace u, v, w jako součin transpozic a ucrčete jejich paritu. Příklad 2.3:
Určete inverzní prvky u−1 , v −1 , w−1 z předešlého příkladu.
Příklad 2.4:
Mějme permutace f, g ∈ Sn . Určete paritu permutace f 7 ◦g 8 ◦f 9 .
Příklad 2.5:
Určete všechny permutace f ∈ S6 , pro něž platí f 2 = (1, 2) ◦ (3, 4).
Příklad 2.6:
Určete všechny permutace a ∈ S8 takové, že a2 = (1, 2, 3) ◦ (4, 5, 6).
Příklad 2.7: V grupě (S5 , ◦) všech permutací pětiprvkové množiny {1, 2, 3, 4, 5} najděte permutaci f takovou, že (1, 3) ◦ (2, 4, 5) ◦ f ◦ (1, 4) = id. Příklad 2.8: Napište permutace f = (2, 3, 4, 5) ◦ (1, 3, 6, 8) a g = (1, 4, 6) ◦ (2, 7, 4, 8, 3) ◦ (1, 5) jako součin 10 transpozic. 8
2. PERMUTACE
9
Příklad 2.9: Dokažte, že permutace (s3 ◦ t−17 )18 ◦ s10 je sudá permutace pro libovolné s, t ∈ S9 .
9
3. GRUPY ZBYTKOVÝCH TŘÍD
3
10
Grupy zbytkových tříd
Definice 3.1: Nechť a, b ∈ Z, řekneme, že a dělí b, pokud ∃c ∈ Z, tak že b = a · c, píšeme a | b. [1, strana 14] Definice 3.2: Nechť a, b ∈ Z. Definujeme největší společný dělitel (a, b) = d, podmínkami: 1. d | a, d | b 2. ∀δ ∈ Z, δ | a, δ | b ⇒ δ | d 3. d ≥ 0 Čísla a, b ∈ Z se nazývají nesoudělná pokud (a, b) = 1. [1, strana 15] Věta 3.3: (Euklidův algoritmus) Nechť a, b ∈ N označme a1 = a, a2 = b a pro n ≥ 3 položme an rovno zbytku po dělení an−2 číslem an−1 . Po konečném počtu kroků dostaneme ak = 0. Pak (a, b) = ak−1 . [1, strana 15] Důsledek: (Bezoutova rovnost) Pro libovolná celá čísla a,b existují celá čísla u,v taková, že a · u + b · v = (a, b). [1, Věta 3.3 (Bezoutova rovnost) strana 15] Definice 3.4: Buď n přirozené číslo. Množiny [a]n = {k · n + a |k ∈ Z}, kde a ∈ Z se nazývají zbytkové třídy podle modulu n. Množinu všech zbytkových tříd podle modulu n označujeme symbolem Zn . [1, Definice 3.7 strana 17] Věta 3.5: Buď n přirozené, a celé číslo. Zbytková třída [a]n má inverzní prvek v (Zn , ·), právě když čísla a, n jsou nesoudělná. [1, Věta 3.13 strana 19] Definice 3.6: Buď 1 < n přirozené číslo. Symbolem ϕ(n) označíme počet všech přirozených čísel menších než n a nesoudělných s n. Funkce ϕ je tzv. Eulerova funkce. Klademe ϕ(1) = 1. [1, Definice 3.15 strana 20] Věta 3.7: Pro libovolné prvočíslo p je ϕ(pk ) = (p − 1) · pk−1 . Pro libovolná nesoudělná přirozená čísla a, b je ϕ(a · b) = ϕ(a) · ϕ(b). [1, Věta 3.16 strana 20] ♣
♣
♣
10
♣
♣
3. GRUPY ZBYTKOVÝCH TŘÍD
11
Úloha i: Pomocí Euklidova algoritmu zjistěte (600, 9432). Řešení: 9432 = 1 · 6000 + 3432 6000 = 1 · 3432 + 2568 3432 = 1 · 2568 + 864 2568 = 2 · 864 + 840 864 = 1 · 840 + 24 840 = 35 · 24 + 0 Největším společným dělitelem je tedy 24. Úloha ii: Dokažte, že čísla 2n + 1 a 9n + 4 jsou nesoudělná pro libovolné n ∈ N. Řešení: Máme vlastně dokázat (2n + 1, 9n + 4) = 1. Použijeme Euklidův algortimus: 9n + 4 = 4 · (2n + 1) + n 2n + 1 = 2 · n + 1 n = n·1+0 Tím je tvrzení dokázáno. Úloha iii: Zjistěte kolik invertibilních prvků má komutativní pologrupa (Z12 , ·). Řešení: Podle věty 1.3.4. je počet prvků majících v (Zn , ·) inverzi roven ϕ(n). Tedy počet inverzních prvků v (Z12 , ·) je roven ϕ(12) = 4. Úloha iv: Určete inverzní prvek ke zbytkové třídě modulo 540, která obsahuje číslo 17. Řešení: Víme, že inverzní prvek exituje, pokud jsou čísla nesoudělná, to nejlépe zjistíme pomocí Euklidova algortimu: 540 = 31 · 17 + 13 17 = 1 · 13 + 4 13 = 3 · 4 + 1 4 = 4·1+0 Zjistili jsme tedy, že čísla jsou nesoudělná a tudíž můžeme hledat inverzní prvek, k tomu využijeme Bezoutovu rovnost: 1 = 13 − 3 · 4 = 13 − 3 · (17 − 13) = −3 · 17 + 4 · 13 = −3 · 17 + 4 · (540 − 31 · 17) = = 4 · 540 − 127 · 17 To znamená, že [17]−1 540 = [−127]540 = [413]540 .
11
3. GRUPY ZBYTKOVÝCH TŘÍD
12
Úloha v: Nalezněte všechna m ∈ N, pro která je ϕ(m) liché. Řešení: 1. Jestliže m je dělitelné lichým prvočíslem p pak p − 1 | ϕ(m) ⇒ ϕ(m) je sudé číslo. 2. Žádné liché prvočíslo nedělí m, pak m = 2k , k ∈ N0 . Je-li k = 0, pak ϕ(m) = ϕ(20 ) = ϕ(1) = 1, je-li k > 0, pak ϕ(m) = ϕ(2k ) = 1 · 2k−1 a to je liché právě, když k = 1. ϕ(m) je liché, jestliže m = 1, 2. Úloha vi: Zjistěte pro která m ∈ N je ϕ(m) = 16. αk α2 1 Řešení: Nechť m = pα 1 ·p2 ·· · ··pk , pi jsou různá prvočísla a αi ∈ N pro i ∈
∈ {1, 2, · · · , k}. 1 −1 2 −1 k −1 ϕ(m) = (p1 − 1) · pα · (p2 − 1) · pα · · · · · (pk − 1) · pα = 16 = 24 , to 1 2 k znamená, že m = 2α · 3β · 5γ · 17δ , α, β, γ, δ ∈ N0 , ϕ(m) = ϕ(2α ) · ϕ(3β ) · ϕ(5γ ) · ϕ(17δ ). Nyní provedeme úvahu jakých hodnot mohou nabývat α, β, γ, δ. Nejlepší je začít u mocniny nejvyššího prvočísla tedy u δ. 1. Je zřejmé, že δ může být nanejvýš rovna 1 a zároveň musí být ϕ(2α )·ϕ(3β )·ϕ(5γ ) = 1, kdyby totiž bylo δ > 1 dostali bychomϕ(m) ≥ 272. Nechť δ = 1 ∧ α = β = γ = 0, pak m = 17 a máme první řešení. Nechť δ = α = 1 ∧ β = γ = 0, pak m = 2 · 17 = 34. Tím jsme vyčerpali všechny možnosti pro δ = 1 a dále v řešení budeme uvažovat δ = 0. 2. Když tedy δ = 0 pak m = 2α · 3β · 5γ , nyní zauvažujeme γ. Kdyby γ ≥ 2 tak ϕ(m) ≥ 20, to znamená, že γ může být nejvýše 1. Nechť tedy γ = 1 ∧ α, β ≥ 1. ϕ(m) = ϕ(2α ) · ϕ(3β ) · ϕ(5) 2α−1 · 2 · 3β−1 · 4 2α−1 · 3β−1 α β A tedy m
= = = = = =
Nechť dále γ = 1 ∧ α = 0 ∧ β ≥ 1. ϕ(m) = ϕ(3β ) · ϕ(5) = 16 2 · 3β−1 · 4 = 16 3β−1 = 2 Nemá řešení. 12
16 16 2 2 1 60
3. GRUPY ZBYTKOVÝCH TŘÍD
13
Dále nechť γ = 1 ∧ β = 0 ∧ α ≥ 1. ϕ(m) = ϕ(2α ) · ϕ(5) 2α−1 · 4 2α−1 α A tedy m
= = = = =
16 16 4 3 40
Tím je γ = 1 a v úvahách budeme pokračovat pro γ = 0. 3. Nyní m = 2α · 3β . Nechť α, β ≥ 1. ϕ(m) = ϕ(2α ) · ϕ(3β ) 2α−1 · 2 · 3β−1 2α−1 · 3β−1 α β A tedy m
= = = = = =
16 16 8 4 1 48
Nechť α = 0 ∧ β ≥ 1. Pak ϕ(m) = ϕ(3β ) = 3β−1 = 8, což nemá řešení. A konečně nechť β = 0 ∧ α ≥ 1. Pak ϕ(m) = ϕ(2α ) = 2α−1 = 16, α = 5 a tedy m = 32. Celkově m = {17, 32, 34, 40, 48, 60}. ♣ TEST:
♣
♣
♣
♣
Rozhodněte zda jsou následující výroky pravdivé:
1. Pro libovolné přirozené číslo m > 2 platí, že ϕ(m) je sudé číslo. 2. Pro libovolné přirozené číslo m platí ϕ(m)2 | ϕ(m2 ). 3. Pro libovoné číslo n ∈ N je (Zn , ·) grupa. 4. Pro libovoné prvočíslo p je (Zp , ·) grupa. 5. Rozhodněte zda je (Z9 , ·) komutativní pologrupa. 6. Pro libovolné prvočíslo p jsou grupy (Z∗p , ·) (grupa zbytkových tříd modulo p neobsahující zbytkovou třídu s reprezentantem [0]p ) a (Z× p , ·) (grupa všech invertibilních zbytkových tříd modulo p) totožné. ♣
♣
♣
♣
♣
Příklad 3.1:
Nalezněte (111, 107) a vyjádřete jej Bezoutovou rovností.
Příklad 3.2:
Pro která n ∈ N jsou čísla 2n − 1 a 9n + 4 nesoudělná?
Příklad 3.3:
Nalezněte inverzní prvek k [49]1000 v (Z1000 , ·).
13
3. GRUPY ZBYTKOVÝCH TŘÍD
14
Příklad 3.4: Rozhodněte, zda existuje inverzní zbytková třída ke třídě obsahující číslo 67 modulo 103 a pokud ano, nalezněte ji. Příklad 3.5: Kolik existuje inverzních prvků v a) (Z1021 , ·)
b)
Příklad 3.6: Vypočítejte: a) ϕ(635)
c) ϕ(1331)
b) ϕ(1221)
(Z4725 , ·)
Příklad 3.7:
Určete pro která n ∈ N platí ϕ(5n ) = 100.
Příklad 3.8:
Dokažte, že pro každé n ∈ N platí ϕ(4n + 2) = ϕ(2n + 1).
Příklad 3.9: Spočtěte: 3 a) [2k +1]−1 v Z22k +1 b) [2k −1]−1 v Z22k +1 c) [m2 −m+1]−1 m3 −1 v Zm −1 22k +1 22k +1 Příklad 3.10:
Zjistěte, pro která m ∈ N je ϕ(m) = 18.
Příklad 3.11: a) n = 24
Určete kolik prvků mají grupy (Z× n , ·) pro následující n: b) n = 306 c) n = 5225
Příklad 3.12: Najděte všechna x ∈ N tak, že 13x dává zbytek 7 po dělění 1000 respektive 100.
14
4. ZÁKLADNÍ VLASTNOSTI GRUP
4
15
Základní vlastnosti grup
Věta 4.1:
Buď G pologrupa s jednotkovým prvkem. Pak platí:
(1) 1−1 = 1, (2) (a−1 )−1 = a, −1 (3) (a1 · a2 · · · · · an )−1 = an−1 · · · · · a−1 2 · a1 ,
kde a, a1 , . . . an jsou libovolné invertibilní prvky z G. [1, Věta 4.6 strana 24] Věta 4.2: Buď (G, ·) pologrupa s jednotkovým prvkem, H množina všech invertibilních prvků z G. Pak (H, ·) je grupa. [1, Věta 4.7 strana 26] Definice 4.3: Řád prvku a grupy G definujeme jako nejmenší přirozené číslo n takové, že an = 1. Pokud takové přirozené číslo neexistuje, řekneme, že řád prvku a je ∞. [1, Definice 4.11 strana 26] Věta 4.4:
Buď G grupa, a ∈ G. Je-li řád prvku a přirozené číslo n, pak :
(1) pro libovolné celé číslo k platí ak = ar , kde r je zbytek po dělení čísla k číslem n, (2) ak 6= am pro libovolná navzájem různá celá čísla 0 < k, m ≤ n. Je-li prvek a řádu ∞, pak: (3) ak 6= am pro libovolná navzájem různá celá čísla k, m. [1, Věta 4.13 strana 26] Věta 4.5: Buď G grupa, a ∈ G a k přirozené číslo. Pak ak = 1 právě, když řád prvku a dělí číslo k.[1, Důsledek 4.14 strana 27] Věta 4.6: Buď G grupa, a ∈ G prvek řádu n, n = k · m. Pak prvek ak je řádu m. [1, Důsledek 4.15 strana 27] Věta 4.7:
Buď G grupa, a, b, c ∈ G. Pak platí: a · b = a · c ⇒ b = c, b · a = c · a ⇒ b = c.
Tyto vztahy se nazývají zákony o krácení. [1, Věta 4.17 strana 27] Definice 4.8: Počet prvků konečné grupy G nazýváme řád této grupy. Označujeme jej symbolem |G|. [1, Definice 6.5 strana 34] ♣
♣
♣
15
♣
♣
4. ZÁKLADNÍ VLASTNOSTI GRUP
16
Úloha i: V grupě (Z× 14 , ·) invertibilních zbytkových tříd modulo 14 spočítejte řád prvku [5]14 . Řešení: • [5]214 = [25]14 = [−3]14 • [5]314 = [−3]14 · [5]14 = [−15]14 = [−1]14 • [1]14 = [−1]214 = ([5]314 )2 = [5]614 Číslo 6 tedy splňuje podmínku [5]614 = [1]14 . Abychom mohli říct, že je řádem prvku [5]614 , musíme dokázat, že je nejmenší přirozené číslo s touto vlastností. Jelikož 4 ani 5 nedělí 6, je podle věty 4.5 řádem prvku [5]14 v grupě (Z× 14 , ·) opravdu 6. Úloha ii: V grupě (Z× 13 , ·) invertibilních zbytkových tříd modulo 13 spočítejte řády všech prvků. Řešení: Jelikož je modul prvočíselný, obsahuje grupa (Z× 13 , ·) dvanáct prvků (obsahuje reprezentanty všech zbytkových tříd modulo 13 kromě zbytkové třídy s reprezentantem 0). Nejlepší je zapisovat si výsledky do tabulky. Prvek [1]13 [2]13 [3]13 [4]13 [5]13 [6]13
Řád 1 12 3 6 4 12
Prvek [7]13 [8]13 [9]13 [10]13 [11]13 [12]13
Řád 12 4 3 6 12 2
(Poznámka: Podrobnější postup hledání řádu prvku viz předešlá úloha.)
• [1]13 - neutrální prvek, je vždy řádu 1 • [2]613 = [64]13 = [−1]13 [2]12 13 = [1]13 • [3]213 = [9]13 = [−4]13 [3]313 = [−12]13 = [1]13 • [4]13 = [2]213 6 [2]12 13 = [4]13 • [5]213 = [25]13 = [−1]13 [5]413 = [2]13 • [6]613 = [46656]13 = [−1]13 [6]12 13 = [1]13 • [7]613 = [117649]13 = [−1]13 [7]12 13 = [1]13 3 • [8]12 13 = [2]13 12 [2]13 = [8]413 • [9]313 = [729]13 = [1]13 • [10]313 = [1000]13 = [−1]13 [10]613 = [1]13 16
4. ZÁKLADNÍ VLASTNOSTI GRUP
17
• [11]613 = [1771561]13 = [−1]13 [11]12 13 = [1]13 • [12]213 = [144]13 = [1]13 ♣ TEST:
♣
♣
♣
♣
Rozhodněte zda jsou následující výroky pravdivé:
1. V libovolné komutativní grupě platí, že řád součinu dvou prvků je roven součinu řádu těchto prvků. 2. Jestliže nějaká grupa obsahuje prvek řádu 6, pak obsahuje i prvek řádu 3. 3. Všechny prvky libovolné nekonečné grupy jsou nekonečného řádu. 4. V libovolné komutativní grupě platí, že řád součinu dvou prvků je roven nejmenšímu společnému násobku řádu těchto prvků. 5. Řád libovolné konečné cyklické grupy je prvočíslo. 6. V libovolné grupě je jen konečně mnoho prvků konečného řádu. 7. Jestliže nějaká grupa obsahuje prvek řádu 2 a též prvek řádu 3, pak obsahuje i prvek řádu 6. 8. V každé grupě platí, že součin libovolných dvou prvků nekonečného řádu je opět prvek nekonečného řádu. 9. Existuje nekonečná grupa s prvkem konečného řádu. 10. Řád prvku a grupy (G, ◦) je roven 1 právě, když a je neutrálním prvkem grupy (G, ◦). 11. V libovolné pologrupě s neutrálním prvkem tvoří množina všech invertibilních prvků grupu. ♣
♣
♣
♣
♣
Příklad 4.1: V grupě (Z× 15 , ·) invertibilních zbytkových tříd modulo 15 spočítejte řád prvku [7]15 . Příklad 4.2: V grupě (GL2 (R), ·) regulárních matic typu 2 × 2 s reálnými prvky určete řád matice A a řád matice B, kde 0 −1 1 1 A= , B= . 1 0 0 1
Příklad 4.3: Určete všechna přirozená čísla m taková, že v aditivní grupě (Z24 , +) zbytkových tříd modulo 24 existuje aspoň jeden prvek řádu m. Příklad 4.4: Určete řád permutace (1, 2, 4, 5) ◦ (3, 7, 8) ◦ (6, 9), respektive (1, 2, 4, 5, 3, 6, 7, 9) ◦ (3, 7, 8) ◦ (6, 2, 9).
17
4. ZÁKLADNÍ VLASTNOSTI GRUP Příklad 4.5: V dané grupě určete řády všech prvků: a) (Z× b) (Z6 , +) 7 , ·)
18
c)
(Z× 6 , ·)
Příklad 4.6: jejich řád.
V grupě (R∗ , ·) nalezněte všechny prvky konečného řádu a určete
Příklad 4.7:
V grupě (C∗ , ·) nalezněte všechny prvky konečného řádu.
Příklad 4.8: a 33.
Určete všechna n ∈ N tak, že v Sn exituje prvek řádu 26,27,32
Příklad 4.9:
Určete řád prvku [k]n v (Zn , +).
Příklad 4.10: grupa.
Dokažte, že konečná pologrupa v níž platí zákony o krácení je
Příklad 4.11: Udejte příklad tříprvkového grupoidu, který není grupou, ale platí v něm zákony o krácení. Ukažte, že grupoid není pologrupou.
18
5. PODGRUPY
5
19
Podgrupy
Věta 5.1: Buď H podgrupa grupy (G, ·). Pak · určuje operaci na množině H a H je grupa vzhledem k této operaci. Je-li navíc grupa G komutativní, pak i H je komutativní grupa. [1, Věta 5.3 strana 29] VětaT5.2: Buďte Hi podgrupy grupy G, kde i probíhá nějakou množinu I 6= ∅. Pak Hi je podgrupa v G. [1, Věta 5.5 strana 29] i∈I
Definice 5.3: Buď M podmnožina grupy G. Symbolem hM i označíme průnik všech podgrup grupy G obsahujících množinu M . Podle předchozí věty je hM i podgrupa grupy G, a sice nejmenší podgrupa grupy G obsahující množinu M . Nazývá se podgrupa generovaná množinou M . Množinu M nazýváme množinou generátorů grupy hM i. Pokud M = {a1 , . . . , an }, pak hovoříme o podgrupě generované prvky a1 , . . . an a označujeme ji stručně ha1 , . . . an i. [1, Definice 5.6 strana 30] ♣
♣
♣
♣
♣
Úloha i: Popište všechny podgrupy grupy (Z, +). Řešení: Podgrupy jsou tvaru k · Z = {k · a |a ∈ Z}, k ∈ N0 . Důkaz: Nechť jsou tedy všechny podgrupy tvaru k · Z = {k · a |a ∈ Z}, k ∈ N0 a H 6= {0} je libovolná podgrupa grupy (Z, +). Ukažme, že H = k · Z. Jelikož H 6= {0} existuje tedy v H alespoň jedno přirozené číslo. Nechť k je nejmenší z přirozených čísel v H. 1) k · Z ⊆ H. Nechť a ∈ Z je libovolné, ukažme, že k · a ∈ H. Je-li a ∈ N dokážeme indukcí: α) a = 1, pak k · a = k · 1 = k ∈ H. β) Předpokládejme, že tvrzení platí pro a = 1, 2, · · · , n a dokážeme pro a = n + 1: k · a = k · (n + 1) = k · n + k ∈ H. Pokud a < 0 pak −k · a = k · (−a) ∈ H. 2) H ⊆ k · Z. Nechť h ∈ H je libovolný. Dělme se zbytkem: h = k · q + r, q, r ∈ Z, 0 ≤ r < k. Z toho, že r = h − k · q ∈ H plyne r = 0. Úloha ii: Určete podgrupu grupy (S4 , ◦) generovanou množinou M = {(1, 2), (1, 3)}. Řešení: • (1, 2) ◦ (1, 3) = (1, 3, 2) • (1, 2) ◦ (1, 3, 2) = (1, 3) • (1, 3) ◦ (1, 3, 2) = (3, 2) • (1, 3, 2)2 = (1, 2, 3)
19
5. PODGRUPY
20
• Dál už nemusíme skládat, protože jsme již dostali grupu, proto hM i = {id, (1, 2), (1, 3), (2, 3), (1, 2, 3), (1, 3, 2)} = {f ∈ S4 |f (4) = 4}. Jelikož množina hM i je uzavřená vzhledem k operaci ◦, obsahuje neutrální prvek a každý prvek v ní má prvek inverzní, je to skutečně podgrupa grupy (S4 , ◦). √
Úloha iii: V grupě (C∗ , ·) určete podgrupu generovanou číslem √ √ Kolik má podgrupa h 22 + i 22 i prvků? √
2 2
√
+i
2 2 .
√
Řešení: Nechť a = 22 + i 22 = cos π4 + i sin π4 . Z Moivrovy věty víme, že (cos π4 + i sin π4 )8 = (cos 8 π4 + i sin 8 π4 ) = 1 a jelikož a je generátorem podgrupy √ √ a řád prvku a je osm ihned víme, že podgrupa h 22 + i 22 i bude mít osm prvků. Dále můžeme dořešit graficky bod a si vyjádříme v goniometrickém tvaru jako cos π4 + i sin π4 a z Moivrovy věty víme, že (cos
π π π π + i sin )k = (cos k + i sin k ). 4 4 4 4
Nyní budeme postupně přičítat úhel osmiúhelník. √
q
2 2
π 4.
√
√
+i
Vzniklých osm bodů tvoří pravidelný
2 2
2 2
−
π 4
2 2
− √
2 2
√
+i
2 2 i
√
={
2 2
√
+i
2 2 ,
√
i, −
♣ TEST:
2 2
√
q
2 2
q
q -1 √
h
i q
√
+i
♣
2 2
√
−i
2 2 ,
♣
q
q -i q
2 2
√
−1, − ♣
2 2
q 1
√
+i
√
+i
2 2
2 2
√
−i
2 2 ,
√
√
−i
√
−i,
2 2
2 2
√
−i
2 2 ,
1}
♣
Rozhodněte zda jsou následující výroky pravdivé:
1. Libovolná podgrupa komutativní grupy je sama komutativní grupou. 2. V grupě nenulových reálných čísel (R∗ , ·) existuje konečná netriviální cyklická podgrupa. 3. Každá netriviální grupa má netriviální komutativní podgrupu. 4. V libovolné grupě (G, ·) platí, že množina všech prvků x ∈ G, pro které je x3 = x2 , tvoří podgrupu grupy (G, ·). 5. V grupě kladných reálných čísel (R+ , ·) existuje netriviální cyklická podgrupa. 6. Každá netriviální podgrupa nekomutativní grupy je nekomutativní. 7. Grupa (Z8 , +) je cyklická. 20
5. PODGRUPY
21
8. Grupa (R∗ , ·) obsahuje dvouprvkovou podgrupu. 9. Každá konečná cyklická grupa o m prvcích má právě ϕ(m) podgrup. 10. Grupa (R, +) obsahuje dvouprvkovou podgrupu. 11. Grupa (C∗ , ·) obsahuje podgrupu řádu 4. 12. Každá komutativní podgrupa grupy (Sn , ◦) je cyklická. ♣
♣
♣
♣
♣
Příklad 5.1: Ukažte, že množina H = {a + b · i | a, b ∈ Z}, kde i = podgrupa v grupě G = (C, +). 0 0 Dále nalezněte podgrupu H grupy G takovou, že H $ H $ C.
√
−1, je
Příklad 5.2:
Popište všechny podgrupy grupy (S3 , ◦).
Příklad 5.3:
V (Z60 , +) určete podgrupu generovanou množinou {[6]60 , [15]60 }.
Příklad 5.4: V grupě (C∗ , ·) všech nenulových komplexních čísel s operací √ násobení určete hi, Θi, tj. podgrupu generovanou množinou {i, Θ}, kde i = −1 a Θ je řešením rovnice t3 = 1, přičemž Θ 6= 1. 2π (nápověda: je vhodné uvážit číslo Θ ve tvaru Θ = cos 2π 3 + i · sin 3 ) Příklad 5.5:
Určete podgrupu grupy (S8 , ◦) generovanou množinou X:
a) X = {(1, 4, 5, 2) ◦ (1, 5, 2, 4, 6, 3), (1, 4, 5, 2) ◦ (4, 5, 6) ◦ (1, 3, 2)}, b) X = {(1, 5, 8) ◦ (1, 4, 2, 5) ◦ (1, 5, 2), (1, 2, 6, 4, 8, 5) ◦ (1, 4, 6, 2)}, c) X = {(1, 8, 2, 3, 5) ◦ (1, 2, 6, 7, 8), (4, 7, 6, 2) ◦ (2, 4, 8)}, d) X = {(1, 2) ◦ (3, 4), (2, 3) ◦ (4, 5)}, e) X = {(2, 4, 6), (4, 7, 2), (3, 2, 4)}. Příklad 5.6:
Určete podgrupu hM i generovanou množinou M = {(1, 2) ◦ (3, 4), (1, 2, 3)}
v grupě (A4 , ◦) všech sudých permutací čtyřprvkové množiny {1, 2, 3, 4}. Příklad 5.7:
Určete podgrupu hM i generovanou množinou M = {([2]8 , [4]8 ), ([6]8 , [4]8 )},
v grupě (Z8 , +) × (Z8 , +). Kolik má podgrupa hM i prvků? Příklad 5.8: √ 3 2.
V grupách (R, +) a (R∗ , ·) určete podgrupu generovanou prvkem
Příklad 5.9:
Určete podgrupu grupy (Z7 , +) generovanou prvkem [2]7 . 21
5. PODGRUPY
22
∗ Příklad 5.10: Ukažte, že dané podmnožiny √ jsou podgrupy √ grupy (R , ·): + + R b) Q c) Q( 3) = {a + b 3 |a, b ∈ Q}.
a)
Příklad 5.11:
Popište všechny podgrupy grupy (Z10 , +).
Příklad 5.12:
Popište všechny podgrupy grupy (Zn , +).
Příklad 5.13:
Nechť P je podgrupa grupy (R∗ , ·), dokažte, že a b MP = |a, b, c, d ∈ R, detMP ∈ P c d
je podgrupa (GL2 (R), ·). Příklad 5.14: Nechť je dána grupa G a její dvě podgrupy H a K. Dokažte, že hH ∪ Ki = {a1 b1 , . . . an bn | n ∈ N, ai ∈ H, bi ∈ K, }.
22
6. IZOMORFISMY A SOUČINY GRUP
6
23
Izomorfismy a součiny grup
Definice 6.1: Buďte G1 , G2 grupy, f : G1 → G2 bijektivni zobrazení. Řekneme, že f je izomorfismus grupy G1 na grupu G2 , jestliže pro libovolné prvky a, b ∈ G platí: f (a) · f (b) = f (a · b). Grupy G1 , G2 se nazývají izomorfní, jestliže existuje izomorfismus G1 → G2 . Skutečnost, že grupy G1 , G2 jsou izomorfní, vyjadřujeme zápisem G1 ∼ = G2 . [1, Definice 6.1 strana 32] Věta 6.2:
Buď f : G1 → G2 izomorfismus grup. Potom platí: f (1) = 1
a pro libovolný prvek a ∈ G1 platí: f (a−1 ) = f (a)−1 . [1, Věta 6.4 strana 34] Věta 6.3: Libovolná nekonečná cyklická grupa je izomorfní grupě Z. Libovolná konečná cyklická grupa řádu n je izomorfní Zn . [1, Věta 6.6 strana 34] Věta 6.4: Buďte G1 , G2 grupy. Definujeme na kartézském součinu G1 × G2 množin G1 a G2 operaci násobení vztahem [a, b] · [c, d] = [a · c, b · d]. Pak (G1 × G2 , ·) je grupa. [1, Věta 6.7 strana 35] Definice 6.5: Grupa (G1 × G2 , ·) se nazývá součinem grup G1 a G2 . [1, Definice 35 strana 35] Věta 6.6: Buď G komutativní grupa a H, K její podgrupy takové, že H ∩K = = {1}. Nechť libovolný prvek a ∈ G lze vyjádřit ve tvaru a = h · k, kde h ∈ H, k ∈ K. Pak G ∼ = H × K. [1, Věta 6.12 strana 36] ♣
♣
♣
♣
♣
Úloha i: Dokažte, že grupy (R∗ , ·) a (R+ , ·) × (Z2 , +) jsou izomorfní. Řešení: Sestrojíme f : R∗ → R+ × Z2 předpisem (r, [0]2 ), r>0 f (r) = (−r, [1]2 ), r<0 Nechť (a, b) ∈ R+ × Z2 libovolné, a ∈ R+ pak f (a) = (a, [0]2 ) a f (−a) = (a, [1]2 ) z toho plyne, že f je surjektivní. Nechť r, s ∈ R∗ takové, že f (r) = f (s), to se nám rozdělí na dva případy 23
6. IZOMORFISMY A SOUČINY GRUP
24
a) (r, [0]2 ) = (s, [0]2 ) a to je právě, když r = s, b) (−r, [1]2 ) = (−s, [1]2 ) a to je právě, když r = s, to znamená, že f je i injektvní, a f je tedy bijektivní. Nechť r, s ∈ R∗ libovolné, f (r) · f (s) = (|r|, x) · (|s|, y) = (|r · s|, x + y), kde [0]2 , r > 0 [0]2 , s > 0 x= ,y= . [1]2 , r<0 [1]2 , s < 0 [0]2 , r >, s > 0 nebo r < 0, s < 0 Tedy x + y = , [1]2 , r < 0, s > 0 nebo r > 0, s < 0 [0]2 , r · s > 0 f (r · s) = f (|rs|, z), kde z = [1]2 , r · s < 0 Tím jsme dokázali, že f je izomorfismus. Úloha ii: Dokažte, že grupa všech otočení pravidelného čtyřstěnu je izomorfní grupě (A4 , ◦). Řešení: Označme si vrcholy pravidelného čtyřstěnu čísly 1, 2, 3, 4. Každé jeho otočení pak můžeme reprezentovat jako permutaci čísel jeho vrcholů. Každé otočení je jednoznačně určeno polohou jedné ze čtyř stěn (čtyři možnosti) a jednoho ze tří vrcholů této stěny (tři možnosti), podle pravidla součinu tedy existuje celkem dvanáct otočení pravidelného čtyřstěnu. Osm z těchto otočení je podle osy procházející vrcholem a těžištěm protilehlé stěny. Tato otočení jsou reprezentována trojcykly (vrchol, jímž prochází osa zůstává na místě). Tři otočení jsou podle os procházejících středy protilehlých stran, ta jsou reprezentována součinem dvojic transpozic. Poslední otočení je identita. Všechny tyto permutace jsou sudé a jejich počet je roven počtu sudých permutací na čtyřprvkové množině. A jistě skládání otočení odpovídá skládání permutací. Tím je dokázáno, že grupa otočení pravidelného čtyřstěnu je izomorfní grupě (A4 , ◦). ♣ TEST:
♣
♣
♣
♣
Rozhodněte zda jsou následující výroky pravdivé:
1. Libovolné dvě šestiprvkové grupy jsou izomorfní. 2. Součin cyklických grup je vždy cyklickou grupou. 3. Součin dvou nekomutativních grup je opět nekomutativní grupa. 4. Libovolné dvě tříprvkové grupy jsou izomorfní. 5. Existuje nekonečně mnoho grup, které jsou navzájem neizomorfní a přitom každá má právě dvě podgrupy. 6. Součin komutativních grup je opět komutativní grupa. 7. Součin libovolné komutativní a libovolné nekomutativní grupy je nekomutativní grupa. 8. Grupy (R, +) a (R+ , ·) jsou izomorfní. 9. Grupy (S3 , ◦) a (D3 , ◦) jsou izomorfní. 10. Každá konečná grupa je izomorfní s grupou permutací vhodné neprázdné konečné množiny. ♣
♣
♣ 24
♣
♣
6. IZOMORFISMY A SOUČINY GRUP Příklad 6.1:
25
V grupě (Z5 × S8 × Z× 7 , ·) spočítejte ([2]5 , (1, 2, 3) ◦ (4, 7), [5]7 ) · ([3]5 , (5, 8), [2]7 ).
Příklad 6.2: Nechť (G, ◦) je grupa a a nějaký její pevně zvolený prvek. Dokažte, že potom (G, ) je také grupa, kde operace je definována předpisem g h = g ◦ a ◦ h. Příklad 6.3: Nechť (A, ◦), (B, ∗) jsou dané grupy. Na množině A × B definujeme operaci ♦ takto: (a1 , b1 )♦(a2 , b2 ) = (a1 ◦ a2 , b1 ∗ b2 ), pro ∀(a1 , b1 ), (a2 , b2 ) ∈ A × B. Dokažte, že: a) (A × B, ♦) je grupa b) grupa (A × B, ♦) je komutativní ⇔ obě grupy (A, ◦), (B, ∗) jsou komutativní. Příklad 6.4: Nechť G je grupa, f : G → G zobrazení, určené předpisem f (x) = x−1 pro libovolné x ∈ G. Dokažte, že f je izomorfismus právě, když G je komutativní. Příklad 6.5:
Dokažte, že (Z× 7 , ·) je izomorfní s (Z6 , +).
Příklad 6.6:
Dokažte, že (Z× 8 , ·) je izomorfní s (Z2 , +) × (Z2 , +).
Příklad 6.7: Buď (G, ·) libovolná konečná grupa. Pro libovolné a ∈ G definujeme zobrazení ψa : G → G předpisem ψa (x) = a · x · a−1 . Dokažte, že pro libovolné a ∈ G je ψa izomorfismus grup. Příklad 6.8: Dokažte, že pro libovolné grupy G a H jsou grupy G × H a H × G izomorfní. Příklad 6.9: Nechť f : G → H je izomorfismus grup. Ukažte, že řády prvku a a f (a) jsou stejné.
25
7. LAGRANGEOVA VĚTA
7
26
Lagrangeova věta
Definice 7.1:
Buď G grupa, H její podgrupa, a ∈ G. Množinu a · H = {a · h | h ∈ H}
nazýváme levá třída grupy G podle podgrupy H (určená prvkem a). [1, Věta 7.1 strana 37] Věta 7.2: Buď G grupa, H její podgrupa, a, b ∈ G. Pak následující tvrzení jsou ekvivalentní: (1) a · H = b · H, (2) a ∈ b · H, (3) b−1 · a ∈ H. [1, Věta 7.2 strana 37] Věta 7.3: (Lagrnageova věta) Řád podgrupy konečné grupy G je dělitelem řádu grupy G. [1, Věta (Lagrangeova věta) strana 39] Věta 7.4: (Fermatova věta) Buď G konečná grupa řádu n, nechť a ∈ G. Pak an = 1. [1, Věta (Fermatova věta) strana 39] Věta 7.5: (Eulerova věta) s n. Pak
Buď n přirozené číslo, buď a celé číslo nesoudělné aϕ(n) ≡ 1 (mod n).
[1, Věta (Euler) strana 39] ♣
♣
♣
♣
♣
Úloha i: Dokažte, že pro každé přirozené číslo n je číslo 22
4n+1
+ 7 složené.
Řešení: Při důkazu, že je číslo složené (lze zapsat jako součin konečného počtu prvočísel) je nejjednodušší najít alespoň jedno prvočíslo, které toto číslo dělí. Zkusíme si dosadit nízká n, tak můžeme odhadnout která prvočísla by to mohla být. Výsledky si zapíšeme do tabulky: 4n+1
22 +7 n 0 11 1 4294967303 = 11 · 390451573 2 11 · . . . 4n+1 Zdá se, že by to mohla být např. 11. Musíme tedy zjistit jestli 11 | 22 + 7. Z důsledku Lagrangeovy věty [1, Důsledek 7.8] a Věty 4.4 (1) víme, že řád čísla 2 v Z× 11 je deset. Při dalším řešení využijeme následující věty. Nechť m ∈ N, a ∈ Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná t, s ∈ N0 platí at ≡ as (mod m) ⇔ t ≡ s (mod r). 26
7. LAGRANGEOVA VĚTA
27
Musíme tedy zjistit s čím je kongruentní 24n+1 modulo 10. Víme, že 24n ≡ 1 (mod 5), podle pravidel pro počítání s kongruencemi víme, že můžeme obě strany kongruence a modul vynásobit tímtéž přirozeným číslem. Tedy 24n 2
4n+1
≡ 1 (mod 5) / · 2 ≡ 2 (mod 10)
z čehož podle uvedené věty plyne 22 22
4n+1
4n+1
24n+1
2
≡ 22 (mod 11) / + 7
+ 7 ≡ 4 + 7 (mod 11) + 7 ≡ 0 (mod 11)
čímž jsme dokázali, že číslo 22
4n+1
+ 7 je složené.
Úloha ii: Určete zbytek po dělení čísla 250 + 350 + 450 číslem 17. 50 50 Řešení: [250 + 350 + 450 ]17 = [250 ]17 + [350 ]17 + [450 ]17 = [2]50 17 + [3]17 + [4]17
• [2]16 17 = 1 Věta 7.5 3·16+2 3 2 [2]50 = ([2]16 17 = [2]17 17 ) · [2]17 = [4]17 • [3]16 17 = 1 3·16+2 3 2 [3]50 = ([3]16 17 = [4]17 17 ) · [3]17 = [9]17 • [4]16 17 = 1 3·16+2 3 2 [4]50 = ([4]16 17 = [4]17 17 ) · [4]17 = [−1]17 • 250 + 350 + 450 = [4]17 + [−1]17 + [9]17 = [12]17 Zbytek je tedy 12. Úloha iii: Popište rozklad grupy (R∗ , ·) podle podgrupy R+ . Řešení: Popsat rozklad znamená zjistit, kdy dvě čísla budou patřit do stejné třídy rozkladu. Nechť tedy a, b ∈ R∗ libovolné a zjišťujeme kdy a · R+ = b · R+ . To je podle věty 7.2 právě, když b−1 ·a ∈ R+ a to může nastat ve dvou případech a) b−1 > 0 což v grupě R∗ znamená, že b > 0 a současně a > 0 nebo b) b−1 < 0 tedy, že b < 0 a současně a < 0 Dvě čísla patří do stejné třídy rozkladu právě, když mají stejné znaménko a rozklad grupy (R∗ , ·) podle podgrupy R+ je tedy na třídy obsahující kladná, respektive záporná reálná čísla, nebo-li R∗ /R+ = {R+ , R− }. ♣
♣
♣
27
♣
♣
7. LAGRANGEOVA VĚTA
28
TEST: 1. Řád grupy (Z7 , +) je 7. 2. Řád grupy (Z∗8 , ·) je 8. 3. Pro každou grupu G, která je řádu 1, platí, že obsahuje pouze neutrální prvek. 4. Řády grupy (Z10 , +) a grupy (Z∗11 , ·) jsou rovny 10. 5. Řády grupy (Zn , +) a grupy (Z× n+1 , ·) jsou shodné pro libovolné n ∈ N. 6. Řády grupy (Zp−1 , +) a grupy (Z∗p , ·) jsou shodné pro libovolné prvočíslo p. ♣ Příklad 7.1:
♣
♣
♣
♣
Určete zbytek po dělení čísla 520 číslem 3.
Příklad 7.2: Určete zbytek po dělení daných čísel číslem 17: 5 13 14 4 c) 1313 + 1414 . a) 540 + 640 + 740 + 840 b) 44 + 55 2n+1
Příklad 7.3:
Dokažte, že pro libovolné n ∈ N je číslo 22
Příklad 7.4:
Popište rozklad grupy (R∗ , ·) podle podgrupy {−1, 1}.
Příklad 7.5:
Popište rozklad grupy (Z, +) podle podgrupy h2i.
+ 3 číslo složené.
Příklad 7.6: Popište levý rozklad grupy (A4 , ◦) sudých permutací na množině {1, 2, 3, 4} podle podgrupy generované permutací (1, 4, 2). Příklad 7.7: Určete počet levých tříd grupy (Z, +) × (Z, +) podle podgrupy H = {(m, n) | 6 | (m − 2n)}. Příklad 7.8: Popište levý rozklad grupy (Z16 , +) podle podgrupy 4Z16 = {4 · a | a ∈ Z16 }. Příklad 7.9: Určete levý rozklad grupy (GL2 (Z2 ), ·) všech regulárních matic nad Z2 podle podgrupy ( ! !) [1]2 [0]2 [1]2 [1]2 H= , . [0]2 [1]2 [0]2 [1]2
28
8. HOMOMORFISMY GRUP
8
29
Homomorfismy grup
Definice 8.1: Buď G1 , G2 grupy. Zobrazení f : G1 → G2 se nazývá homomorfismus grupy G1 do grupy G2 , jestliže splnňuje podmínku: f (a) · f (b) = f (a · b). [1, Definice 8.1 strana 41] Definice 8.2: Buď f : G1 → G2 surjektivní homomorfismus. Pak grupa G2 se nazývá homomorfní obraz grupy G1 . [1, Definice 8.7 strana 42] Definice 8.3:
Buď f : G1 → G2 homomorfismus grup. Množina J(f ) = {x ∈ G1 | f (x) = 1}
se nazývá jádro homomorfismu f . [1, Definice 8.10 strana 42] Věta 8.4: Homomorfismus f : G1 → G2 je injektivní právě, když J(f ) = {1}. [1, Věta 8.11 strana 43] ♣
♣
♣
♣
♣
Úloha i: Je dán předpis f : (Z3 , +) → (S4 , ◦), kde f ([a]3 ) = (1, 2) ◦ (3, 4) ◦ (1, 2, 3)a . Rozhodněte, zda korektně zadává zobrazení a zda se jedná o homorfismus. Řešení: Zjistit zda se jedná o korektně zadané zobrazení znamená dokázat, že nezáleží na volbě reprezentantů téže zbytkové třídy. To znamená zjistit zda platí rovnost f ([a]3 ) = (1, 2) ◦ (3, 4) ◦ (1, 2, 3)a = (1, 2) ◦ (3, 4) ◦ (1, 2, 3)a+3k , k ∈ Z, protože (1, 2, 3) je řádu 3. Rovnost tedy platí a předpis korektně definuje zobrazení. Nyní zjistíme, zda se jedná o homomorfismus. Nebo-li ověříme platnost rovnosti f ([a]3 + [b]3 ) = f ([a]3 ) ◦ f ([b]3 ), ale např. f ([1]3 + [2]3 ) = (1, 2) ◦ (3, 4) ◦ (1, 2, 3)1+2 = (1, 2) ◦ (3, 4). f ([1]3 ) ◦ f ([2]3 ) = (1, 2) ◦ (3, 4) ◦ (1, 2, 3)1 ◦ (1, 2) ◦ (3, 4) ◦ (1, 2, 3)2 = (1, 3) ◦ (2, 4). Vidíme, že dané zobrazení není homomorfismus. ♣
♣
♣
♣
♣
TEST: 1. Pro libovolné dvě grupy (G, ·) a (H, ·) existuje homomorfismus grupy (G, ·) do grupy (H, ·). 2. Homomorfismus grup je injektvní, je-li jeho jádro jednoprvkové. 3. Libovolný surjektivní homomorfismus grup má alespoň dvouprvkové jádro. 4. Existuje surjektivní homomorfismus grupy konečného řádu do grupy nekonečného řádu. 29
8. HOMOMORFISMY GRUP
30
5. Pro libovolné dvě grupy (G, ·) a (H, ·) existuje surjektivní homomorfismus grupy (G, ·) do grupy (H, ·). 6. Pro každý homomorfismus platí, že jeho jádro obsahuje neutrální prvek. 7. Je-li f : G → G homomorfismus grup, pak pro každý prvek a ∈ G platí, že prvky a a f (a) mají stejný řád. 8. Pro libovolnou grupu (G, ·) platí, že množina všech homomorfismů f : G → G spolu s operací skládání zobrazení je pologrupa s neutrálním prvkem. ♣
♣
♣
♣
♣
Příklad 8.1: Rozhodněte, zda dané předpisy korektně definují zobrazení a zda se jedná o homomorfismus nebo dokonce izomorfismus grup. a) α : (Z4 , +) × (Z3 , +) → (Z12 , +), kde α(([a]4 , [b]3 )) = [a − b]12 , b) β : (Z4 , +) × (Z3 , +) → (Z12 , +), kde β(([a]4 , [b]3 )) = [6a + 4b]12 , c) γ : (Z∗3 , ·) × (Z5 , +) → (Z5 , +), kde γ(([a]3 , [b]5 )) = [b|a| ]5 , d) δ : (Z15 ) → (Z5 , +) × (Z3 , +), kde δ([a]15 ) = ([a]5 , [a]3 ), e) : (Q∗ , ·) → (Q∗ , ·), kde (p/q) = q/p. Příklad 8.2:
Určete obrazy a jádra homomorfismů z předešlého příkladu.
Příklad 8.3: Dokažte, že zobrazení α grupy (Z30 , +) do grupy (Z20 , +) definované předpisem α([a]30 ) = [6a]20 je homomorfismus grup, dále dokažte, že zobrazení β grupy (Z20 , +) do grupy (S6 , ◦) definované předpisem β([b]20 ) = = (1, 2, 3, 4, 5)b je také homomorfismus grup. Nakonec určete jádra homomorfismů a) J(α) b) J(β) c) J(β ◦ α). Příklad 8.4: Je dáno zobrazení α grupy (Z6 , +) do grupy (S6 , ◦) předpisem α([a]6 ) = (1, 2, 3) ◦ (1, 2, 3)α ◦ (1, 2, 3) pro libovolné celé číslo a a zobrazení β grupy (Z3 , +) × (Z4 , +) do grupy (Z6 , +) předpisem β(([b]3 , [c]4 )) = [2b + 3c]6 pro libovolná celá čísla b, c. Rozhodněte, zda se jedná o homomorfismy a určete následující jádra homomorfismů. a) J(α) b) J(β) c) J(α ◦ β). Příklad 8.5: Spočtěte jádro a obraz homomorfismu α z grupy (Z× 36 , ·) do grupy (Z× , ·) daného předpisem α([a] ) = [27a − 26] , kde a ∈ Z. 36 108 108 Příklad 8.6: Dokažte, že předpis f [a]20 = (1, 2, 3, 4, 5)a definuje homomorfismus f : (Z20 , +) → (S7 , ◦). Příklad 8.7: Nechť G je grupa, f : G → G zobrazení, určené předpisem f (x) = x · x pro libovolné x ∈ G. Dokažte, že f je homomorfismus právě,když G je komutativní.
30
8. HOMOMORFISMY GRUP
31
Příklad 8.8: Buď (G, ·) libovolná konečná grupa. Pro libovolné a ∈ G definujeme zobrazení ψa : G → G předpisem ψa (x) = a · x · a−1 . Dokažte, že zobrazení Ψ : G → S(G) dané předpisem Ψ(a) = ψa je homomorfismus grupy (G, ·) do grupy (S(G), ◦) všech permutací množiny G. Příklad 8.9: jícího tvaru
Uvažme grupu (G, ·) 1 a G= 0 1 0 0
matic typu 3/3 nad Z, které jsou následu b c | a, b, c ∈ Z , 1
kde · je násobení matic. Definujeme nyní zobrazení f : (G, ·) → (Z, +), které matici 1 a b 0 1 c 0 0 1 přiřadí číslo a − c. Dokažte, že zobrazení f je homomorfismus grup. Příklad 8.10: Kolik jich je?
Popište všechny homomorfismy grupy (S3 , ◦) do grupy (Z8 , +).
31
9. FAKTOROVÉ GRUPY
9
32
Faktorové grupy
Definice 9.1:
Podgrupa H grupy G se nazývá normální, jestliže a · h · a−1 ∈ H
pro libovolné prvky a ∈ G, h ∈ H. [1, Definice 9.1 strana 45] Věta 9.2: Buď G grupa, H její normální podgrupa. Definujme součin dvou levých tříd a · H, b · H grupy G podle H vztahem (a · H) · (b · H) = (a · b) · H. Pak · je operace na množině G/H a (G/H, ·) je grupa. [1, Věta 9.4 strana 46] Věta 9.3:
Buď G grupa, H její normální podgrupa. Pak zobrazení p : G → G/H dané vztahem p(a) = a · H
je surjektivní homomorfismus. Jeho jádro je rovno H. [1, Věta 9.5 strana 46] Definice 9.4: Grupa (G/H, ·) se nazývá faktorová grupa grupy G podle podgrupy H. Homomorfismus p se nazývá projekce grupy G na faktorovou grupu G/H. [1, Definice 9.6 strana 46] Věta 9.5: (Hlavní věta o faktorových grupách)Buď f : G1 → G2 homomorfismus grup a H normální podgrupa v G1 taková, že H ⊆ J(f ). Pak existuje jediný homomorfismus f¯ : G1 /H → G2 , jehož složení f¯ ◦ p : G1 → G1 /H → G2 s projekcí p je rovno homomorfismu f. f
(G1 , ·) @ p@
- (G2 , ·) f¯
@ R @ (G1 /H, ·) [1, Věta 9.10 (Hlavní věta o faktorových grupách) strana 47] Věta 9.6: Buď f : G1 → G2 surjektivní homomorfismus grup. Pak grupy G2 a G1 /J(f ) jsou izomorfní. [1, Věta 9.11 strana 48] ♣
♣
♣
♣
♣
Úloha i: Rozhodněte zda podgrupa generovaná transpozicí (1, 2) je normální podgrupa v (S3 , ◦). Řešení: Transpozice (1, 2) generuje podgrupu H = {(1, 2), id} grupy (S3 , ◦). Protože platí (1, 2, 3) ◦ (1, 2) ◦ (3, 2, 1) = (2, 3) 6∈ H, není podgrupa H normální. 32
9. FAKTOROVÉ GRUPY
33
Úloha ii: Uvažme grupu všech regulárních matic řádu 2 s racionálními prvky (GL2 (Q), ·). Označme SL2 (Q) množinu všech těch matic z GL2 (Q), které mají determinant 1: SL2 (Q) = {A ∈ GL2 (Q) | |A| = 1}. a) Dokažte, že množina SL2 (Q) je podgrupou grupy GL2 (Q). b) Dokažte, že množina SL2 (Q) je normální podgrupou grupy GL2 (Q). c) Popište, jak vypadá a čemu je izomorfní faktorgrupa GL2 (Q)/SL2 (Q). Řešení: ad a) Nechť A, B ∈ SL2 (Q) libovolné. Pak |A · B| = |A| · |B| = 1 · 1 = 1 a množina SL2 (Q) je tedy uzavřena na operaci násobení matic. 1 0 ∈ SL2 (Q). Jistě 0 1 Jelikož pro libovolnou regulární matici A platí |A−1 | = |A|−1 tak také pro každou matici B ∈ SL2 (Q) platí, že B −1 ∈ SL2 (Q). Dokázali jsme, že SL2 (Q) je skutečně podgrupou (GL2 (Q), ·). ad b) Nechť A ∈ (GL2 (Q), ·), H ∈ SL2 (Q). |A · H · A−1 | = |A| · |H| · |A−1 | = = |A| · |A−1 | = 1. To znamená, že A · H · A−1 ∈ SL2 (Q) a množina SL2 (Q) je pak normální podgrupa (GL2 (Q), ·). ad c) Popsat jak vypadá rozklad GL2 (Q)/SL2 (Q), znamená určit, kdy dvě matice A, B ∈ GL2 (Q) leží ve stejné třídě rozkladu. Tedy kdy A · SL2 (Q) = B · SL2 (Q), to je podle věty 7.2 právě, když B −1 ·A ∈ SL2 (Q) tedy, když |B −1 ·A| = 1, což je ekvivalentní |B −1 |·|A| = 1 a to je shodné s |A| = |B|. Dvě matice tedy náleží do stejné třídy rozkladu pokud mají stejný determinant. Abychom mohli zjistit čemu je izomorfní faktorgrupa GL2 (Q)/SL2 (Q) musíme najít surjektivní homomorfismus grup h : GL2 (Q) → K jehož jádrem je SL2 (Q). Jelikož již víme jak vypadá rozklad GL2 (Q)/SL2 (Q), určíme grupu K a předpis h tak, že zjistíme, jak na množině GL2 (Q)/SL2 (Q) vypadá operace ·. Označíme si Mr = {A ∈ GL2 (Q) | |A| = r} třídu rozkladu, jejíž matice mají determinant roven r. Nechť A ∈ Ma , |A| = a a B ∈ Mb , |B| = b libovolné, pak A · B = C, jelikož |A| · |B| = |A · B| = |C| = a · b, a tedy C ∈ Ma·b , tedy Ma · Mb = Ma·b . Operace · na množině GL2 (Q)/SL2 (Q) tedy vypadá jako násobení čísel v grupě (Q∗ , ·). Potom zbývá dokázat, že h : (GL2 (Q), ·) → (Q∗ , ·), h(A) = |A| je surjektivní homomorfismus, jehož jádrem je SL2 (Q). 1. Homomorfismus: h(A · B) = |A · B| = |A| · |B| = h(A) · h(B), 2. h je surjektivní: zřejmé, 3. J(h) = SL2 (Q): J(h) = {A ∈ GL2 (Q) | |A| = 1} = SL2 (Q). Tím jsme dokázali, že GL2 (Q)/SL2 (Q) je izomorfní Q∗ .
33
9. FAKTOROVÉ GRUPY
34
Úloha iii: Nalezněte čemu je izomorfní faktorgrupa komplexních čísel podle podgrupy realných čísel (C/R ∼ = ?). Řešení: Stejně jako v předešlé úloze musíme najít surjektivní homomorfismus h : (C, +) → (K, ·) jehož jádrem je R. Grupa (K, ·) je pak ona hledaná grupa izomorfní faktorgrupě (C/R, +). Grupu K a předpis h opět určíme tak, že zjistíme jak vypadá rozklad C/R a jak na něm vypadá operace +. Rozklad určíme následovně: Nejprve si napíšeme jak vypadají levé třídy rozkladu (a + i · b) + R = {(a + i · b) + r | r ∈ R}, nyní zjistíme, kdy dvě komplexní čísla (a + i · b) a (¯ a + i · ¯b) patří do stejné třídy ¯ rozkladu. Tedy, kdy (a + i · b) + R = (¯ a + i · b) + R. To je právě, když (−¯ a − i · ¯b) + (a + i · b) ∈ R a to je jen tehdy, když b − ¯b = 0 nebo-li b = ¯b. Označíme si Rb = {a + i · b | a ∈ R} pak C/R = {Rb | b ∈ R}. Protože Rb ·R¯b = {a+i·b | a ∈ R}·{¯ a +i·¯b | a ¯ ∈ R} = {(a+¯ a)+i·(b+¯b)} = Rb+¯b , vidíme, že hledanou grupou K je (R, +) a předpis h : (C, +) → (R, +), h(a + i · b) = b. Zbývá tedy dokázat, že h je surjektivní homomorfismus s J(h) = R. 1. Homomorfismus: h((x + i · y) + (a + i · b)) = h(x + a + i · (y + b)) = a + b = = h(x + i · y) + h(a + i · b), 2. h je surjektivní: zřejmé, 3. J(h) = R : J(h) = {(a + i · b) ∈ C | h(a + i · b) = 0, a, b ∈ R} = = {a + i · b | a ∈ R, b = 0} = R. Tím jsme dokázali, že (C/R, +) ∼ = (R, +). ♣
♣
♣
♣
♣
TEST: 1. Libovolná faktorgrupa cyklické grupy je cyklickou grupou. 2. V libovolné grupě platí, že každá její normální podgrupa je komutativní. 3. Je-li f : G → H homomorfismus grupy (G, ·) do grupy (H, ·), potom grupa (H, ·) je izomorfní s nějakou faktorgrupou grupy (G, ·). 4. V libovolné grupě platí, že každá její podgrupa je normální. 5. V libovolné grupě platí, že každá její komutativní podgrupa je normální. 6. Pro libovolnou grupu (G, ·) a libovolnou její normální podgrupu H platí: Je-li (H, ·) komutativní, potom je faktorgrupa (G/H, ·) komutativní. ♣
♣
♣
♣
♣
Příklad 9.1: Rozhodněte, zda je hM i normální podgrupa grupy (S4 , ◦), M = {(1, 3), (3, 4)}.
34
9. FAKTOROVÉ GRUPY Příklad 9.2:
35
Mějme následující podgrupy grupy (S6 , ◦) G = {f ∈ S6 | f sudá} H = {f ∈ G | f (3) = 3}
tedy H ⊂ G ⊂ S6 . Rozhodněte, zda a) H je normální podgrupa grupy (G, ◦) b) H je normální podgrupa grupy (S6 , ◦) c) G je normální podgrupa grupy (S6 , ◦) Příklad 9.3: V komutativní grupě (G, ·) uvažme podmnožinu D všech prvků, jejichž druhá mocnina je neutrální prvek e: D = {x ∈ G | x · x = e}. Dokažte, že D je a) podgrupa grupy (G, ·), b) normální podgrupa grupy (G, ·). Příklad 9.4: Popište všechny normální podgrupy grup (S3 , ◦) a (A4 , ◦). Ukažte, že grupa (An , ◦) je normální podgrupa grupy (Sn , ◦) pro libovolné n ∈ N. Příklad 9.5: ných čísel
Buď dána grupa (G, ◦) nekonstantních afinních zobrazení reálG = {f : R → R | f (x) = ax + b, a ∈ R∗ , b ∈ R}
s operací skládání zobrazení ◦. Uvažme v této grupě dvě podgrupy: T = {f : R → R | f (x) = ax, a ∈ R∗ } S = {f : R → R | f (x) = x + b, b ∈ R} Která z nich je normální podgrupou grupy (G, ◦)? Příklad 9.6: Uvažujme normální podgrupu grupy (G, +) = (Z, +) × (Z, +) definovanou takto: a) H = {(a, b) ∈ Z × Z | 2 | a, 3 | b}, b) H = {(a, b) ∈ Z × Z | 7 | 2a + 3b}. Určete, která grupa (K, ·) je izomorfní faktorgrupě G/H, dále definujte vhodné zobrazení ϕ : G → K, pro něž dokážete, že ϕ je surjektivní homomorfismus grup, jehož jádrem je H. Příklad 9.7: V komutativní grupě (G, ·) s neutrálním prvkem e uvažme podmnožinu K všech prvků grupy G konečného řádu, tedy K = {x | ∃n ∈ N , xn = e}. Dokažte, že a) K je normální podgrupa grupy (G, ·), b) ve faktorgrupě (G/K, ·) mají všechny prvky (mimo neutrální) stejný řád. 35
9. FAKTOROVÉ GRUPY
36
Příklad 9.8: Uvažme množiny reálných čísel G = {3p 15q | p, q ∈ Z}, a H = {3r | r ∈ Z} a operaci · (násobení reálných čísel). Zřejmě (G, ·) je grupa. a) ukažte, že H je normální podgrupa v G, b) popište faktorgrupu G/H, které grupě je izomorfní? Příklad 9.9: Nechť je dána grupa matic (G, ·) (s operací násobení matic) a její normální podgrupa H. Určete faktorgrupu G/H: a 0 a 0 ∗ ∗ G= | a, c ∈ Q , b ∈ Q , H = | a, c ∈ Q , b ∈ Q, a, c > 0 . b c b c
Příklad 9.10:
Víme, že množina ε a G= | ε = {−1, 1}, a ∈ Z 0 1
společně s operací násobení matic tvoří grupu (G, ·). Označme 1 2b H= |b∈Z 0 1 podmnožinu množiny G. Ukažte, že H je normální G.Popište podgrupa grupy ε a ε¯ a ¯ rozklad G/H tj. charakterizujte kdy dvě matice a náleží 0 1 0 1 do stejné třídy rozkladu. Určete počet tříd rozkladu G/H. Určete, které grupě (K, ·) je izomorfní faktorgrupa G/H tj. popište grupu (K, ·) a definujte vhodné zobrazení α : G → K pro něž dokažte, že α je surjektivní homomorfismus grup, jehož jádrem je H. Příklad 9.11: Nechť (G, ·) je grupa. Pro libovolné a, b ∈ G definujeme [a, b] = = a−1 · b−1 · a · b. Dokažte, že množina ¯ = {[a1 , b1 ] · · · · · [an , bn ] | n ∈ N, a1 , . . . an , b1 , . . . , bn ∈ g} G ¯ ·) je komutativní. je normální podgrupa grupy G a že faktorgrupa (G/G,
36
10. KONEČNÉ GRUPY
10
37
Konečné grupy
Definice 10.1:
Množina C = {a ∈ G | a · x = x · a pro libovolné x ∈ G}
se nazývá centrum grupy G. [1, Definice 10.4 strana 49] Věta 10.2:(Sylow) Buď G konečná grupa a p prvočíslo takové, že jeho k−tá mocnina dělí řád grupy G. Pak G obsahuje podgrupu řádu pk . [1, Věta 10.8 (Sylow) strana 50] Věta 10.3:(Sylow) Buď G konečná grupa, p prvočíslo a k největší celé číslo takové, že pk dělí řád grupy G. Buď r počet podgrup řádu pk v grupě G. Pak r ≡ 1 mod p. [1, Věta 10.8 (Sylow) strana 50] Definice 10.4: Nechť p je prvočíslo a G je konečná komutativní grupa. pSylowská podgrupa grupy G je libovolná její podgrupa o pk prvcích, kde k je největší přirozené číslo s vlastností pk | |G|. Definice 10.5: Buď p prvočíslo. Grupy řádu pk , kde k > 0, se nazývají pgrupy. [1, Definice 10.11 strana 52] Věta 10.6:
Buď G konečná komutativní grupa, |G| > 1. Pak G∼ = Zpk1 × · · · × Zpkmm , 1
kde p1 , . . . , pm jsou prvočísla a k1 , . . . , km jsou přirozená čísla. Tento rozklad grupy G na součin netriviálních cyklických p-grup je určen jednoznačně, až na pořadí činitelů. [1, Věta 10.13 strana 52] ♣
♣
♣
♣
♣
Úloha i: Popište všechny (až na izomorfismus) komutativní grupy o 12 prvcích. Řešení: Vyřešit tento příklad znamená, zjistit kolika způsoby lze číslo 12 napsat jako součin mocnin prvočísel (ne nutně různých). 12 = 22 · 3 = 2 · 2 · 3. Existují tedy právě dvě komutativní grupy o 12 prvcích: Z4 × Z3 a Z2 × Z2 × Z3 . Úloha ii: Nalezněte všechny 3-Sylowské podgrupy grupy (S5 , ◦). Řešení: |S5 | = 5! = 120 = 23 · 3 · 5 Největší mocnina trojky, která dělí 120 je 31 . 3-Sylowská podgrupa bude mít tedy tři prvky. Je to například podgrupa h(1, 2, 3)i = h(1, 3, 2)i. Označme si S množinu všech 3-Sylowských podgrup. S = {h(k, l, m)i | k, l, m ∈ {1, 2, 3, 4, 5} ∧ k 6= l 6= m 6 k}.
37
10. KONEČNÉ GRUPY
38
Přičemžh(k, l, m)i = h(k, m, l)i = h(l, k, m)ih(l, m, k)i = h(m, k, l)ih(m, l, k)i. 5! = 120 |S| = 53 = 3!·2! 12 = 10, existuje tedy deset 3-Sylowských podgrup grupy (S5 , ◦) ♣
♣
♣
♣
♣
TEST: 1. Je-li počet prvků nějaké grupy prvočíslo, pak je tato grupa komutativní. 2. Každá konečná komutativní grupa je izomorfní vhodnému součinu konečných cyklických grup. 3. Je-li řád konečné grupy (G, ·) dělitelný prvočíslem p, pak grupa (G, ·) obsahuje prvek řádu p. ♣ Příklad 10.1:
♣
♣
♣
♣
Určete centrum grupy
a) (S3 , ◦) všech permutací tříprvkové množiny b) (Z7 , +) zbytkových tříd modulo 7 c) (GL2 (Q), ·) regulárních matic 2 × 2 nad racionálními čísly. Příklad 10.2: prvcích.
Popište všechny (až na izomorfismus) komutativní grupy o 120
Příklad 10.3: fismus)?
Kolik existuje komutativních grup o 32 prvcích (až na izomor-
Příklad 10.4:
Nalezněte alespoň jednu 2-Sylowskou podgrupu grupy (S5 , ◦).
38
Výsledky příkladů 1
Pojem grupy
TEST: 1.1
1.ano, 2.ne, 3.ne.
a) ne,
b) ano,
c) ne,
d) ano.
1.3 a) není komutativní, není asociativní, nemá neutrální prvek, b) je komutativní, není asociativní, prvek d je neutrální. 1.4
· e f g
e f g e
f g e f
g e f g
1.6 (G, ◦) je nekomutativní pologrupa, která nemá neutrální prvek. Bude-li množina G jednoprvková pak (G, ◦) bude triviální komutativní grupa. 1.7
a) ano,
1.8
Je asociativní, neexistuje neutrální prvek, není grupou.
1.9
Je asociativní, neexistuje neutrální prvek, není grupou.
1.10
1.11
◦ f1 f2 f3 f4 f5 f6
f1 f1 f2 f3 f4 f5 f6
b) ne,
f2 f2 f1 f5 f6 f3 f4
f3 f3 f6 f1 f5 f4 f2
c) ne,
f4 f4 f5 f6 f1 f2 f3
f5 f5 f4 f2 f3 f6 f1
d) ano,
f6 f6 f3 f4 f2 f1 f5
Ne, nejedná se o grupu.
39
e) ano,
f) ano.
VÝSLEDKY PŘÍKLADŮ
2
40
Permutace
TEST:
1.ano, 2.ano, 3.ne, 4.ne, 5.ne, 6.ne, 7.ne.
2.1 a) f = (1, 9, 5)◦(2, 3, 7)◦(4, 8, 6), g = (1, 8, 4, 2)◦(3, 5, 6), h = (1, 6, 7, 2, 9, 5, 4, 3), b) p(f ) = 1, p(g) = −1, p(h) = −1, c) f 100 ◦ g 100 = (3, 1, 9, 5, 4, 8, 6, 7, 2). 2.2 a) u = (1, 3, 7, 8, 6, 9, 5)◦(2, 4), v = (1, 5, 3)◦(6, 8), w = (1, 8, 9, 2)◦(3, 4, 6, 7, 5) b) u◦v = (2, 4)◦(5, 7, 8, 9), v◦u = (2, 4)◦(3, 7, 6, 9), w◦v = (1, 3, 8, 7, 5, 4, 6, 9, 2), c) w ◦ v ◦ u = (1, 8, 9, 4) ◦ (2, 6) ◦ (3, 5), w ◦ v ◦ w = (1, 7, 4, 9) ◦ (2, 3, 6, 5, 8), v ◦ w ◦ u = (1, 4, 5, 6, 2, 8, 7, 9), d) v 103 = (1, 5, 3) ◦ (6, 8), e) w27 = (1, 2, 9, 8) ◦ (3, 6, 5, 4, 7), f) u120 ◦ v −3 = (1, 3, 7, 8, 9, 5), g) v 32 ◦ w32 = (1, 6) ◦ (1, 3) ◦ (4, 5) ◦ (4, 7), sudá h) u = (1, 5) ◦ (1, 9) ◦ (1, 6) ◦ (1, 8) ◦ (1, 7) ◦ (1, 3) ◦ (2, 4), lichá v = (1, 3) ◦ (1, 5) ◦ (6, 8), lichá w = (1, 2) ◦ (1, 9) ◦ (1, 8) ◦ (3, 5) ◦ (3, 7) ◦ (3, 6) ◦ (3, 4), lichá. 2.3 u−1 = (1, 5, 9, 6, 8, 7, 3) ◦ (2, 4), v −1 = (1, 3, 5) ◦ (6, 8), w−1 = (1, 2, 9, 8) ◦ (3, 5, 7, 6, 4). 2.4
Sudá.
2.5 f1 = (1, 3, 2, 4), f2 = (1, 4, 2, 3), f4 = (1, 4, 2, 3) ◦ (5, 6).
f3 = (1, 3, 2, 4) ◦ (5, 6),
2.6 a1 = (1, 4, 2, 5, 3, 6), a2 = (1, 5, 2, 6, 3, 4), a3 = (1, 6, 2, 4, 3, 5), a4 = (1, 3, 2) ◦ (4, 6, 5), a5 = (1, 4, 2, 5, 3, 6) ◦ (7, 8), a6 = (1, 5, 2, 6, 3, 4) ◦ (7, 8), a7 = (1, 6, 2, 4, 3, 5) ◦ (7, 8), a8 = (1, 3, 2) ◦ (4, 6, 5) ◦ (7, 8). 2.7
f = (2, 4, 5)−1 ◦ (1, 3)−1 ◦ (1, 4)−1 = (1, 2, 5, 4, 3).
3
Grupy zbytkových tříd
TEST:
1.ano, 2.ne, 3.ne, 4.ne, 5.ano, 6.ano.
3.1
(111, 107) = 1, 1 = 27 · 111 − 28 · 107.
3.2
n 6= 9 + 17 · k | k ∈ Z. 40
VÝSLEDKY PŘÍKLADŮ
41
3.3
[49]−1 1000 = [449]1000 .
3.4
Existuje, je to zbytková třída [20]103 .
3.5
a) 1020,
3.6
a) 504,
3.7
n = 3.
b) 2160. b) 720,
c) 1210.
3.9 a) [1 + (2k − 1)(2k−1 )]22k +1 , 3 c) [1 + m 2−m ]m3 −1 . 3.10
m = {19, 27, 38, 54}.
3.11
a) 8,
3.12
a) x ≡ 539 (mod 1000),
4
b)96,
b) [−1 − (2k + 1)(2k−1 )]22k +1 ,
c) 3600. b)x ≡ 39 (mod 100).
Základní vlastnosti grup
TEST:
1.ne, 2.ano, 3.ne, 4.ne, 5.ne, 6.ne, 7.ne, 8.ne, 9.ano, 10.ano, 11.ano.
4.1
4.
4.2
Řád matice A je 4, řád matice B je ∞.
4.3
m ∈ {1, 2, 3, 4, 6, 8, 12, 24}.
4.4
12, respektive 14.
4.5
a)
4.6
Číslo 1 je řádu 1, číslo -1 je řádu 2, ostatní čísla jsou řádu ∞.
4.7
2π Je jich nekonečno, jsou to všechny prvky tvaru (cos 2π n + i sin n ), n ∈ N.
4.9
Označme d = (n, k), pak řád prvku je
Prvek [1]7 [2]7 [3]7 [4]7 [5]7 [6]7
Řád 1 3 6 3 6 2
b)
Prvek [0]6 [1]6 [2]6 [3]6 [4]6 [5]6
41
Řád 1 6 3 2 3 6
n d.
c)
Prvek [1]6 [5]6
Řád 1 2
VÝSLEDKY PŘÍKLADŮ
5
42
Podgrupy
TEST: 12.ne.
1.ano, 2.ano, 3.ano, 4.ano, 5.ano, 6.ne, 7.ano, 8.ano, 9.ne, 10.ne, 11.ano.
5.2
S3 , {id}, {id, (1, 2)}, {id, (1, 3)}, {id, (2, 3)}, {id, (1, 2, 3), (1, 3, 2)}.
5.3
h[3]60 i.
5.5 a) hXi = h{(1, 2, 5) ◦ (4, 6, 3), (1, 3) ◦ (2, 4) ◦ (5, 6)} = {((1, 2, 5) ◦ (4, 6, 3))i ◦ ((1, 3) ◦ (2, 4) ◦ (5, 6))j | i = 0, 1, 2, j = 0, 1}, b) hXi = h{(1, 8, 5), (2, 4)}i = {(1, 8, 5)i ◦ (2, 4)j | i = 0, 1, 2, j = 0, 1}, c) hXi = h{(1, 3, 5), (2, 6, 7), (4, 8)}i, d) hXi = {(1, 2, 4, 5, 3)i ◦ ((1, 2) ◦ (3, 4))j | i = 0, 1, 2, 3, 4, j = 0, 1}, e) hXi = {f ∈ A8 | f (1) = 1, f (5) = 5, f (8) = 8}. 5.6
hM i = A4 .
5.7 4.
hM i = {([0]8 , [0]8 ), ([2]8 , [4]8 ), ([4]8 , [0]8 ), ([6]8 , [4]8 )} = h([2]8 , [4]8 )i, |hM i| =
5.8
V (R, +) {k ·
5.9
(Z7 , +).
6
Izomorfismy a součiny grup
TEST:
√ 3
√ k 2 | k ∈ Z}, v (R∗ , ·) { 3 2 | k ∈ Z}.
1.ne, 2.ne, 3.ano, 4.ano, 5.ano, 6.ano, 7.ano, 8.ano, 9.ano, 10.ne.
6.1
([0]5 , (1, 2, 3) ◦ (4, 7) ◦ (5, 8), [3]7 ).
7
Lagrangeova věta
TEST:
1.ano, 2.ne, 3.ano, 4.ano, 5.ne, 6.ano.
7.1
1.
7.2
a) 15,
7.4
R∗ /{1, −1} = {{a, −a} |a ∈ R+ }.
7.5
Z2 .
b) 15,
c) 14.
7.6 {id, (1, 2, 4), (1, 4, 2)}, {(1, 2)◦(3, 4), (2, 3, 4), (1, 3, 4)}, {(1, 3)◦(2, 4), (1, 4, 3), (1, 2, 3)}, {(1, 4) ◦ (2, 3), (1, 3, 2), (2, 4, 3)} .
42
VÝSLEDKY PŘÍKLADŮ 7.7
43
6.
7.8 {[0]16 , [4]16 , [8]16 , [12] 16 }, {[1]16 , [5]16 , [9]16 , [13]16 }, {[2]16 , [6]16 , [10]16 , [14]16 }, {[3]16 , [7]16 , [11]16 , [15]16 } 7.9
H,
8
Homomorfismy grup
TEST:
[0]2 [1]2
[1]2 [0]2
[0]2 , [1]2
[1]2 [1]2
,
[1]2 [1]2
[0]2 [1]2
[1]2 , [1]2
[1]2 [0]2
1.ano, 2.ano, 3.ne, 4.ne, 5.ne, 6.ano, 7.ne, 8.ano.
8.1 a) není zobrazení, mus, e) izomorfismus.
b) homomorfismus, c) není zobrazení, d) izomorfis-
8.2 b) O(β) = {[c]12 | 2 | c}, J(β) = {([a]4 , [b]3 ) | 12 | 6a + 4b}, d) O(δ) = Z5 × Z3 , J(δ) = {[0]15 }, e) O() = Q∗ , J() = {1}. 8.3 a) J(α) = {[a]30 | 20 | 6a}, b) J(β) = {[b]20 | 5 | b}, c) J(β ◦ α) = 5Z30 . 8.4 a) Zobrazení α není homomorfismus, b) J(β) = {([b]3 , [c]4 ) | 6 | 2b + 3c}, c) Zobrazení α ◦ β není homomorfismus. 8.5 J(α) = {[a]36 | a ∈ Z, (a, 36) = 1, [27a−2]108 = [1]108 } = {[1]36 , [5]36 , [13]36 , [17]36 , [25]36 , [29]36 }, O(α) = {[27a − 2]108 | a ∈ Z, (a, 36) = 1} = {[1]108 , [55]108 }. 8.10
9
Právě dva.
Faktorové grupy
TEST:
1.ano, 2.ne, 3.ne, 4.ne, 5.ne, 6.ne.
9.1
Není.
9.2
a) ne,
9.5
S.
b) ne, c) ano.
9.6 a) K = (Z2 × Z3 ), ϕ((a, b)) = ([a]2 , [b]3 ) b) K = (Z7 , +), ϕ((a, b)) = [2 · a + 3 · b]7 9.8 b) Dvě čísla patří do stejné třídy rozkladu, pravě když q = q¯, G/H ∼ = Z. 9.9
Z2 × Z2 . 43
VÝSLEDKY PŘÍKLADŮ
44
9.10 Dvě matice patří do stejné třídy rozkladu právě, když = ¯ a 2 | a + a ¯,je izomorfní grupě Z∗ × Z2 .
10
Konečné grupy
TEST:
1.ano, 2.ano, 3.ano.
10.1
a) {id},
10.2
Z2 × Z2 × Z2 × Z3 × Z5 ,
10.3
7.
b) Z7 ,
c)
k 0
0 k
|k∈Q . ∗
Z2 × Z3 × Z4 × Z5 ,
Z3 × Z5 × Z8 .
10.4 Jsou to osmiprvkové podgrupy, např. {id, (1, 3), (2, 4), (1, 2, 3, 4), (1, 4, 3, 2), (1, 2)◦ (3, 4), (1, 4) ◦ (2, 3), (1, 3) × (2, 4)} - grupa symetrií čtverce.
44
Literatura [1] J. Rosický: Algebra, MU, Brno 2002, 4.vydání [2] O. Klíma: Cvičení - jaro 2003, www.math.muni.cz/∼klima [3] R. Kučera: Písemky ke zkoušce z minulých let, www.math.muni.cz/∼kucera [4] P. Horák: Cvičení z algebry a teoretické aritmetiky I, MU, Brno 1998, 2.vydání [5] J. Weil: Rozpracovaná řešení úloh z vyšší algebry, Academia, Praha 1987 [6] G. Birkhoff, S. Mac Lane: Prehľad modernej algebry (slovenský překlad), ALFA, Bratislava společně s SNTL, Praha 1979 [7] O. Borůvka: Základy teorie grupoidů a grup, Československá akademia věd, Praha 1962
45