MV008 — Algebra I — Cvičení Podstatná část příkladů je převzata od kolegů, jmenovitě Prof. Kučery, Doc. Poláka a Doc. Kunce, se kterými jsem v minulosti při přípravě cvičení spolupracoval. Sbírka vznikla modifikací sbírek, které používám při cvičení k předmětu Algebra I na PřF, který nemá ovšem úplně identický obsah. Veškeré připomínky, opravy a komentáře jsou vítány na adrese klima@math.muni. cz. Hvězdičkou jsou označeny doplňující úlohy, které přesahují sylaby předmětu nebo jsou obtížnější. Ondřej Klíma Verze z 17. září 2019 0 Opakování modulární aritmetiky (z předmětu MB104) Příklad 0.1: Určete největšího společného dělitele dvojice čísel: 1) 2016,2017, 2) 1000,1024, 3) 153,221. Příklad 0.2: Nalezněte koeficienty do Bezoutovy rovnosti pro dvojice čísel 1) 1000,1024, 2) 153,221, 3) 49,225. Příklad 0.3*: Pro libovolné přirozené číslo k, určete největšího společného dělitele dvojice čísel: 1) 2fe + l,22fe + l, 2) k3 - í,k2 -k+ 1. Příklad 0.4*: Pro libovolné přirozené číslo k, určete koeficienty do Bezoutovy rovnosti pro dvojici k3, k2 — 1. Příklad 0.5: Určete hodnotu Eulerovy funkce pro následující čísla n: 1) n = 24, 2) n = 306, 3) n = 5225. Příklad 0.6: Ukažte, že pro libovolné n > 2 je ip(n) sudé číslo. Příklad 0.7*: Určete všechna přirozená čísla m, pro která platí (p(m) = 18. Příklad 0.8*: Určete všechna přirozená čísla n taková, že ip(n) | n. Příklad 0.9: Určete zbytek po dělení daných čísel číslem 17. 1) 250 + 350 + 450 , 2) 540 + 640 + 740 + 840 , 3) 444 + 55\ 4) 1313'3 + 1515'5 Příklad 0.10: Ukažte, že číslo 260 + 730 je dělitelné číslem 13. Příklad 0.11: Určete zbytek po dělení čísla ag9~3l° číslem 44, pro a = 8, 9,10,11. Příklad 0.12: Určete poslední dvě cifry čísla 151515. Příklad 0.13: Určete poslední tři cifry čísla 151515. Příklad 0.14: Určete poslední dvě cifry čísla 131313. Příklad 0.15*: Dokažte, že pro libovolné n e N je 22 + +3 číslo složené. Příklad 0.16*: Dokažte Čínskou zbytkovou větu: Nechť je dáno k e N a fc-tice m\,--- ,m,k po dvou nesoudělných přirozených čísel. Pak pro libovolnou fc-tici c\, ■ ■ ■ ,Ck přirozených čísel existuje x G N takové, že x = Ci(modTOi) pro i = 1,.. ., k. Navíc je toto x určeno jednoznačně modmi.....to^; přesněji, všechna tato čísla dávají stejný zbytek po dělení číslem m\.....m^. 1 1 Pologrupy Příklad 1.1: Rozhodněte, zda dané předpisy zadávají operaci / na množině všech racionálních čísel případně na množině všech nenulových racionálních čísel Q* = Q — {0}. 1) f(x,y) = pro ijeQ, 2) /(f,i) 3) f(x,y)-- 4) 5) /(?,§) = pro p,q,r,s eZ, q^O^ s. \Í2 ■ x + y, pro x,y G Q, P+r g+s pro p,reZ, g, s £ N. pro p,g,r,seZ,g^0^s. 6) /(f.7) = V?.ProP.9.r'aeZ. QŕOŕs- 7) J(f,i) = ^Proí^,SeZ\{0}. Příklad 1.2: Rozhodněte, zda daný grupoid je pologrupa, případně monoid a zda je operace komutativní. 1) Celá čísla s operací sčítání. 2) Reálná čísla s operací násobení. 3) Celá čísla s operací odečítání. 4) Přirozená čísla s operací největší společný dělitel. Příklad 1.3: Pro dané množiny matic typu 2 krát 2 nad reálnými čísly rozhodněte, zda je sčítání, resp. násobení, matic operací na této množině. Pokud se jedná o operaci, zjistěte, zda je operace asociativní či komutativní a zda obsahuje neutrální prvek. 1) Množina všech matic nad celými čísly. 2) Množina všech matic nad racionálními čísly. 3) Množina všech regulárních matic nad racionálními čísly. 4) Množina všech matic s nulou v levém dolním rohu a s jedničkami na diagonále. 5) Množina všech regulárních matic nad celými čísly. Příklad 1.4: Pro množinu X značíme V(X) množinu všech podmnožin množiny X. Pro následující operace určete, zda grupoid V(X) je pologrupou, zda je operace komutativní a zda existuje neutrální prvek. 1) Průnik. 2) Sjednocení. 3) Množinový rozdíl. (Y \ Z = {x eY \ x g Z}) 4) Symetricky rozdíl. (Y ^ Z = (Y \ Z) U {Z \ Y)) Příklad 1.5: Určete, zda operace na tříprvkové množině {a, b, c} daná tabulkou je komutativní, asociativní a zda má neutrální prvek. 1) o a b c a b a a b a b a c a a a 2) o a b c a b a a b a b c c a c a 3) o a b c a a a a b b b b c c c c 2 Příklad 1.6*: Prvek e pologrupy (G, •) se nazývá idempotent, jestliže e • e = e. Ukažte, že každá konečná pologrupa obsahuje aspoň jeden idempotent. Příklad 1.7: Pro množinu X označme 1Z(X) množinu všech relací na X, tj. 1Z(X) = V(X x X). Na 1Z(X) definujeme operaci o takto: Dokažte, že (lZ(X),o) je monoid. Víme, že speciálním případem relací jsou zobrazení, pro které je operace o skládání zobrazení. Označme T(X) množinu všech transformací množiny X (zobrazení z X do X), tj. T(X) = {/ e K(X) | (V* G X)(3y e X)((x, y) e f A (Vy')((x, y') e / y' = y))} . Rozhodněte, zdaje (T(-X"),o) monoid. Podobně značíme VT{X) množinu všech parciálních transformací na X, tj. PTpO = {/ G I (Vx, y, z e X)(((x, y) e / A (x, z) e /) y = z)} . (Všimněme si, že T(X) C VT(X) a že prázdná relace patří do VT(X).) Rozhodněte, zdaje VT{X) podpologrupa/podmonoid pologrupy/monoidu (72.(X),o). Příklad 1.8: Uvažujme monoid všech transformací množiny přirozených čísel: (T(N),o). Rozhodněte, zda dané podmnožiny tvoří podpologrupu, resp. podmonoid. 1) I — podmnožina všech injektivních zobrazení z N do N. 2) S - podmnožina všech surjektivních zobrazení z N do N. 3) B - podmnožina všech bijektivních zobrazení z N do N. 4) C = {/ e T (N) I /(l) = 1}. 5) D = {/ e T(N) | f2 = idj,}. 6) E = {f e T(N) | Vn e N : f (n) > n}. 7) F = {f e T(N) | Vn e N : 2|/(n) - n}. 8) G = {/ G T (N) | Vn e N : 2 //(n) - n}. Příklad 1.9: Uvažujme monoidy všech matic 2 krát 2 nad reálnými čísly (MaÍ2(M),+) a (MaÍ2(M), .). Pro každou podmnožinu množiny Mat2(R) z následujícího seznamu rozhodněte, zda tvoří podpologrupu, resp. pod- monoid (Mat2(R),+) či (Mat2(R),.). 1) Mi = Maí2(Q). 2) M2 = {Ae Mat2(R) \ \A\ = 0}. 3) M3 = {Ae Mat2(R) \ \A\ ^ 0}. 4) M4 = {A e Maí2(R) | |A| G Q}. 5) M5 = {A e Maí2(M) | \A\ > 1}. po U {(x, y)eX xX \ (3ze X)((x, z) e cr A (z, y) e p)} . 3 8) M8 = j(^0 \a,deRJ. 9) M9 = |^ ^ |a,6,ceKJ. V případě 8) zkuste využít odpovědí z části 6) a 7). Příklad 1.10: Doplňte následující tabulku operace na tříprvkové množině tak, aby výsledný grupoid byl pologrupou. o a b c a b a c b c Příklad 1.11: Následující tabulku je možno jediným způsobem doplnit na tabulku operace • v pologrupě (S, •), kde S = {a, b, c, d, e, /}. a b c d e f a a b c d f b b e c d b f c c c f c c d d d c d d f e e b c d e f f f f d f f c 1) Určete, kterému prvku z množiny S se rovná d ■ b, resp. a ■ e, v pologrupě (S, •). 2) * Určete všechny idempotenty. 3) * Vypište všechny pravé neutrální prvky. 4) * Vypište všechny levé nulové prvky. 5) Lze původní tabulku doplnit tak, aby byla operace • v grupoidu (S, •) komutativní? Příklad 1.12*: V monoidu T(X) z příkladu 1.7. určete počet všech idempotentů. Příklad 1.13*: V monoidu matic (MaÍ2(M), •) typu 2 krát 2 nad reálnými čísly s operací násobení matic určete všechny idempotenty. (Zkuste kromě aritmetického postupu zapojit i geometrickou představu a znalosti z MB101.) Příklad 1.14*: Dokažte, že pro pologrupu (S, •) jsou následující podmínky ekvivalentní: (i) (Va, i) £ 5) a ■ b ■ a = a, (ii) (Va G S) a ■ a = a A (Va, b, c G S) a • b ■ c = a ■ c, (iii) (Va, i) £ 5) a ■ b = b ■ a a = b. Poznamenejme, že pologrupa splňující tyto podmínky se nazývá rektangulární band. Příklad 1.15*: Buď A konečná abeceda a uvažujme množinu všech jazyků nad A, tj. množinu V (A*). Podmnožiny této množiny tvořené všemi regulárními, resp. všemi bezkontextovými jazyky, označíme 1Z£Q(A), resp. CF(Ä). Rozhodněte, zda 1Z£Q(A), resp. CF(Ä), jsou podmonoidy monoidu (V(A*), •), (V(A*), Li), resp. (V(A*), n). Pokud je pro Vás příklad příliš jednoduchý, uvažujte podmnožinu tvořenou lineárními jazyky (to jsou jazyky dané bezkontextovou gramatikou, kde každé pravidlo na pravé straně obsahuje nejvýše jeden neter-minál) nebo si zvolte svoji vlastní složitější třídu jazyků. 4 Příklad 1.16: Určete podpologrupu pologrupy (N,+), resp. (N, •), generovanou dvojicí prvků 5 a 7. Totéž pro dvojici 10 a 15 a dvojici 12 a 18. Příklad 1.17: uvažujme množinu Mat2(R) všech matic typu 2 krát 2 nad reálnými čísly. V pologrupách (Mat2(R),+), resp. (Mat2(R), ■), určete podpologrupy generované následující množinou prvků X. 1) X 2) X 3) X 4) X 5) X 1 1 0 1 1 1 0 1 0 -1 1 o 1 1 0 1 1 -1 0 1 -1 o 0 -1 1 1 1 o Příklad 1.18: Buď (S, •) pologrupa a M = {mi,m2,..., mk} její neprázdná konečná podmnožina taková, že její prvky po dvou komutují (tj. platí Vs, ŕ G M : s ■ t = t ■ s). Dokažte, že potom podpologrupa generovaná množinou M je rovna množině {mfnij1 • • • mT I £i< f2.....efe G N0, ei + e2 + • • • + efe > 0} . Příklad 1.19: Určete všechny konečné podpologrupy pologrupy: 1) (M,-), 2)*(C, •). Příklad 1.20: Určete podmonoid monoidu T({1, 2, 3}) generovaný prvky / a g, kde transformace jsou zadány takto: f (í) = 2, f (2) = 1, /(3) = 2, g(í) = 2, g(2) = 3, g(3) = 3. Příklad 1.21: Určete všechny prvky přechodového monoidu následujícícho automatu. a a í ) a, b b b ~ Příklad 1.22: Dokážte, že zobrazení a : (C, •) —>• (Mat2(M.), ■) dané předpisem a(a + bi) libovolná a, b e R, je injektivní homomorfismus pologrup. -b pro Příklad 1.23: Určete, které z následujících předpisů zadávají homomorfismus ip z pologrupy (Maí2(K),+), resp. (Mat2(R), ■), do pologrupy (R, +), resp. (R, •)■ 1) if(A) = \A\, kde \A\ značí determinant matice A, 2) ip(A) = tr{Ä), kde tr(Á) značí stopu matice A, tj. tr( 3) tp( ( ^ I) = a, pro a, b,c,d E R, a b c d 5 4) (N0,+), a(n) = \n\. 2) /3:(N,+)^(C,-),/3(n)=2". 3) 7 : 0P(N), íl) -í- ('P(N), U), 7(X) = Xc = N \ X. 4) 5 : (N, •) (N, •), 5(n) = n2. 5) e : (N,nsd) ->• (N, nsd), e(n) = n2. 6) C : (-<4*;') ~~(^4*;C(M) = m2; kde A je konečná abeceda a u libovolné slovo. 7) rj : (V(A), -=-) —>• (No, +), Tj(X) = \X\. Zde A je konečná množina a \X\ značí počet prvků množiny X. 8) # : ('P(.A), -=-) —>• (Z2, +), 0(-X") = [|-X"|]2. Zde A je konečná množina a |X| značí počet prvků množiny X. Pokud je odpověď pozitivní, tj. jedná se o homomorfismus, rozhodněte, zda je zobrazení také izomorrismus. Příklad 1.25: Rozhodněte, zda jsou následující dvojice pologrup izomorfní. 1) (C, •) a (R, •). 2) (R, •) a (Z, +). 3) (N,+) a (N, •). 4) (N, +) a (Z-, +), kde Z~ je množina všech záporných celých čísel. 5) (Q,+) a (Q, •)■ 6) (Q, •) a (K,.). 7) ({0,l},-)a(7>({0}),U). 8) (Mat2QBL),+) a (C, •)■ 9) (Mat2(R),+) a (M, •)• 10)* (N, •) a (L, •), kde L je množina všech lichých přirozených čísel. 11) ({«}+•) a (N,+). 12) (S, •) a ({a, 6, c, d}+, •), kde S1 je podpologrupa pologrupy ({a, •) tvořená slovy sudé délky. Příklad 1.26: Dejte příklad injektivního homomorfismu z pologrupy (N, +) x (N, +) do pologrupy (N, •). Příklad 1.27*: Dejte příklad izomorfismu z pologrupy (N, •) x (N, •) do pologrupy (N, •). Příklad 1.28: Dokažte, že neexistuje injektivní homomorfismus z pologrupy (N,+) x (N,+) do pologrupy (Z,+). 6 Příklad 1.29*: Dokažte, že neexistuje injektivní homomorfismus z pologrupy (N,+) x (N,+) do pologrupy ({a, b}+,-). Příklad 1.30: Nalezněte injektivní homomorfismus 1) z pologrupy ({a, b, c}+, •) do pologrupy ({a, b}+, ■); 2) z pologrupy (Z, +) do pologrupy (MaÍ2(M), +); 3) z pologrupy (Z,+) do pologrupy (MaÍ2(R), ■); 4) z pologrupy (N, •) do pologrupy (MaÍ2(M),+); 5) z pologrupy (N, •) do pologrupy (MaÍ2(M), •)■ Příklad 1.31: U každého z následujících předpisů (kde a, b G Z, x, y G N, p, g G Z \ {0}) rozhodněte, zda zadává zobrazení. Pokud ano, rozhodněte, zda se jedná o homomorfismus či dokonce izomorfismus pologrup. Určete dále, které z nich jsou homomorfismy či dokonce izomorfismy monoidů. a,ä: (Z4,+) x (Z3,+) (Z12,+) «((H4, Ma)) = [6a + 4Ď]12 ä(([a]4, [%)) = [a - 6]i2 /3:(N0,+)x(N,-)^(N,-) /3((x,y))=y* 7:(Q\{0},-)^(Q\{0},-) 7(p/g) = g/p 5: (Zi5,-) -> (Z5,-) x (Z3,-) 5(Hi5) = ([a]5, [a]3) Příklad 1.32*: Určete všechny dvouprvkové pologrupy (až na izomorfismus, tj. přejmenování prvků). 2 Grupy 2.1 Definice a základní vlastnosti Příklad 2.1: Rozhodněte, zda daný grupoid (G, o) je grupa. 1) G je množina nenulových racionálních čísel a operace o je dána předpisem x o y = \x ■ y\. 2) G je interval (0,1) a operace o je dána předpisem x o y = x + y — [x + y], kde [z] značí celou část z čísla z, tj. nej větší celé číslo menší nebo rovno z. 3) G je množina celých čísel a operace o je dána předpisem x o y = x + (—\)xy. 4) G = R x R — {(0, 0)} je množina všech dvojic reálných čísel z nichž aspoň jedno je nenulové, a operace o je dána předpisem (x, y) o (u, v) = (xu — yv, xv + yu). 5) G = (R — {0}) x R je množina uspořádaných dvojic reálných čísel, přičemž první z nich není 0, a operace o je dána předpisem (x, y) o (u, v) = (xu, xv + y). 7 6) G je množina komplexních čísel, jejichž reálná i imaginární část je celočíselná, a operace o je sčítání komplexních čísel. 7) G = R je množina všech reálných čísel a operace o je dána vztahem x o y = —xy, x < 0, y < 0 \xy\, jinak pro x, y G 8) G = {(a, 6) G R x R \ a2 + b2 = 1} a operace o je dána předpisem (a, b) o (c, ď) = (ad + bc, bd — ac) pro (a, 6), (c, d) G G. 9) G = {(a, 6) G R x M | a2 + b2 > 1} a operace o je dána předpisem (a, 6) o (c, d) = (ad + bc, bd — ac) pro (a,b), (c, d) G G. 10) G = {(a, 6) G Z x Z | a2 — 5b2 = 1} a operace o je dána předpisem (a, b) o (a', b') = (aď + 566', ab' + a'b) pro (a, 6), (a', 6') G G. Příklad 2.2: Popište multiplikativní tabulku grupy (Z* , •) pro následující n: l)n = 5, 2)n = 7, 3) n = 8. Příklad 2.3: Spočtěte 1) [4] 15 v ^15' 2) [17] 181 v ^181' 3) [49] 226 v ^226' 4) [49] 225 v ^225' 5) [125]121g6 v ä1296. Příklad 2.4: 1) Dokažte, že v libovolné grupě platí tzv. zákony o krácení (Va, 6, c) (ab = ac 6 = c) A (Va, 6, c) (6a = ca 6 = c) . 2) Popište, jak lze z multiplikativní tabulky operace poznat, že v grupoidu platí zákony o krácení. 3)* Dokažte, že konečná pologrupa, v které platí zákony o krácení, je grupa. 4) Udejte příklad nekonečné pologrupy, která není grupou, ale platí v ní zákony o krácení. 5) 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. 6) Udejte příklad pětiprvkového grupoidu s neutrálním prvkem, který není grupou, ale platí v něm zákony o krácení. Ukažte, že grupoid není pologrupou. Příklad 2.5: Určete, kolik je dvouprvkových, resp. tříprvkových, resp. čtyřprvkových grup (až na izomorfis-mus, tj. přejmenování prvků). Příklad 2.6: Dokažte, že v konečné grupě o sudém počtu prvků existuje prvek, který je inverzní k sobě samému a není to neutrální prvek. Příklad 2.7: Doplňte tabulku operace * tak, aby vznikla grupa ({a, 6, c}, *): o a 6 c a 6 c a c Příklad 2.8: Nechť (G, o) 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 o a o h. 8 Příklad 2.9*: Dokažte, že grupy jsou právě ty pologrupy, pro něž platí: (Va, b) (3x, y) (ax = b, ya = b) . 2.2 Grupa permutací Příklad 2.10: Nechť _(\ 2345678 9\ A 2345678 9\ S_lv3 4 7 2 1 9 8 6 5J 1 \5 2 1 4 3 8 7 6 9/ ' _/l 2345678 9\ W — ^8 14637592y" 1) Rozložte permutace s, ŕ, m na součin nezávislých cyklů. 2) Spočtěte součiny s o ŕ, t o s, s o u o t. Použijte jak "dvojřádkový"zápis, tak rozklad na nezávislé cykly. 3) Spočtěte s3,s20,r3,tW3,u211. 4) Určete inverzní prvky s-1, ŕ-1, 5) Spočtěte permutace (s120 o t~3)17 o u23 a (w~23 o s)134 o t4. 6) Permutace s, t, u rozložte na součin transpozic a určete jejich paritu. Příklad 2.11: Napište permutace / = (2,3,4,5) o (1,3,6,8) a g = (1,4,6) o (2,7,4,8,3) o (1,5) jako součin 10 transpozic. Příklad 2.12: Dokažte že permutace (s3 o t~17)18 o s10 je sudá permutace pro libovolné permutace s, t e §9. Příklad 2.13: Rozhodněte, zda existuje permutace s e §9 taková, že s o (1, 2, 3) = (1, 2) o s. Příklad 2.14: Určete všechny permutace a z grupy §§ takové, že a2 = (1, 2, 3)(4, 5, 6). Podobně určete b takové, že b4 = (1,2,3,4,5,6,7), c takové, že c3 = (1, 2, 3,4)(5, 6, 7, 8), d takové, že d2 = (1, 2, 3, 4)(5, 6, 7, 8) a e takové, že e2 = (1,2,3,4) . Příklad 2.15: Určete všechny permutace / z grupy §§ takové, že /3 = (1, 2)(3,4)(5, 6). Příklad 2.16: Určete, pro která přirozená čísla n e N existuje permutace s e §6 taková, že so (1, 2, 3,4, 5)os = (1, 2)™. Pro tato n popište všechny takové permutace s. Příklad 2.17: Buď a e §m cyklus délky n.Dokažte, že pro libovolné k G N platí: 1) ak = íd právě když n dělí k, 2) pokud n nedělí k pak je ak součinem d nezávislých cyklů délky -j, kde d je největší společný dělitel n a k. Příklad 2.18*: 1) Ukažte, že libovolnou permutaci v §„ lze rozložit na součin transpozic tvaru 2) Ukažte, že libovolnou sudou permutaci v §„ lze rozložit na součin cyklů tvaru (1, 2, i). Příklad 2.19*: Ukažte, že libovolnou permutaci v §„ lze rozložit na součin cyklů (1,2) a (1,2,... ,n). Příklad 2.20*: Dokažte, že pro každou konečnou množinu X existuje trojice /, g, h transformací této množiny taková, že podmnožina {f,g, h} generuje celou pologrupu T(X). 9 Příklad 2.21*: Určete, které prvky s£§„ lze psát ve tvaru b2c2 pro vhodné b, c e §„. 2.3 Rád prvku Příklad 2.22: Určete řád permutace (1,2, 4, 5) o (3, 7, 8) o (6, 9) resp. (1,2,4, 5, 3, 6, 7, 9) o (3, 7, 8) o (6, 2, 9). Příklad 2.23: Určete největší Á- e N takové, že v grupě §i0 existuje prvek řádu k. Příklad 2.24: Nalezněte nějaké k G N takové, že v grupě §i5 existuje prvek řádu k, ale v grupě §14 prvek řádu k neexistuje. Příklad 2.25: Určete řád prvku [k]n v grupě (Z„,+). Příklad 2.26: Určete řády všech prvků v grupě (Z* , •) pro n = 7, 8,12,13. Příklad 2.27: Určete řády prvků [2]17 a [13]i7 v (Zf7, •)■ Příklad 2.28: V GL2(Z3) (grupa regulárních matic nad Z3) určete řády prvků ^ ^ a 2.4 Podgrupy Příklad 2.29: Ukažte, že podmnožina kladných reálných čísel, resp. kladných racionálních čísel, resp. Q(v/3) = {a + bVŠ | a,i)€Q,s2 + ř)2>0} je podgrupa grupy (R*, ■). Příklad 2.30: Ukažte, že množina sudých permutací tvoří podgrupu grupy §„ pro libovolné ra G N. Příklad 2.31: Popište všechny podgrupy grupy (Zi0, +)■ Příklad 2.32: Popište všechny podgrupy grupy (Z, +). Příklad 2.33: Popište všechny podgrupy grupy (Z„, +). Příklad 2.34: Popište všechny podgrupy grupy §3, respektive grupy A4. Příklad 2.35*: Popište všechny podgrupy grupy symetrií D„ (alespoň pro n = 3, 4). Příklad 2.36: Uvažujme grupu (§n, °) všech permutací množiny N. Rozhodněte, zda dané podmnožiny tvoří podgrupu grupy (§K, o): 1) iři = {/ € §N I Vra e N : f (n) > n}. 2) H2 = {/ e §N I P = id}. 3) H3 = {f e §N I 3ra e N : /" = id}. 4) H4 = {f e §M I Vra G N : f(2n) = 2ra}. Příklad 2.37: Pro libovolnou podmnožinu X množiny N označíme dvě podmnožiny Spj takto: Sx = {/ e §n I Vx e X : f (x) =x}, Tx = {/ e §N | Vx e N : x e X f (x) e X}. Rozhodněte, zda podmnožina Sx, resp. Tx, tvoří podgrupu grupy (§pj,o). 10 Příklad 2.38: Určete podgrupu §g generovanou množinou X: 1) X = {(4, 5, 2,1) o (4, 6, 3,1, 5, 2), (4, 5, 2,1) o (4, 5, 6) o (2,1, 3)}, 2) X = {(1,5, 8) o (1,4, 2, 5) o (1, 5,2), (1,2, 6,4, 8,5) o (1,4, 6,2)}, 3) X = {(1,8, 2,3, 5) o (1, 2,6,7, 8), (4, 7,6, 2) o (2,4,8)}, 4) X = {(1,2)(3,4),(2,3)(4,5)}. 5)* X = {(2,4, 6), (4, 7, 2), (3, 2,4)}. Příklad 2.39*: Určete podgrupu §„ generovanou množinou {(1, 2), (1,2,3,..., n)}. Příklad 2.40: V (Z;+) určete podgrupu generovanou množinou {8,30}. Příklad 2.41: V (Z60,+) určete podgrupu generovanou množinou {[6]eo, [15]6o}- Podobně v (Z50,+) určete podgrupu generovanou množinou {[24] 50, [30] 50}. Příklad 2.42: V grupě (M,+), resp. (R*, •), určete podgrupu generovanou prvkem Příklad 2.43: Nechť je dána grupa G a její dvě podgrupy H a K. Dokažte, že (HUK) = {aibi ... anbn | n e N, at e H,bl e K}. 2.5 Homomorfismy a izomorfismy grup Příklad 2.44: Dokažte, že (Z7 , •) je izomorfní s (Z6, +) a (Zg , •) je izomorfní s (Z2, +) x (Z2, +). (Ukažte, že předpis /([a]6) = [3]" definuje izomorŕismus / : (Z6,+) —>• (Z%,+).) Příklad 2.45: U homomornsmů z příkladu 1.23 určete jádro a obraz homomorŕismu a rozmyslete si znovu otázku, zda je dané zobrazení izomorŕismem.. Příklad 2.46: Dokažte, že předpis /(H20) = (1,2,3,4,5)° definuje homomorfismus grup / : (Z20,+) —> (§7, o). Určete jeho jádro a obraz. Příklad 2.47: Nechť / : G —» H je izomorŕismus grup. Ukažte, že řády prvků a a f (a) jsou stejné. Co lze říci o řádech prvků a a f (a) v případě, že / : G —> ií je (injektivní) homomorfismus? Příklad 2.48: Popište všechny homomorfismy z grupy (Z3, +) do grupy (A4, o). Příklad 2.49: Popište všechny injektivní homomorfismy z grupy (Z2, +) x (Z2, +) do grupy (A4, o), respektive (§4, o). Příklad 2.50: Pro libovolnou grupu (G, •) označme Aut(G) = {/ : G —> G | / izomorfismus} množinu všech autoniorfismů grupy G a End(G) = {/ : G —» G | / homomorfismus} množinu všech endomorfismů grupy G. Ukažte, že (End(G),o), kde o je skládání zobrazení, je monoid a Aut(G) je podmnožina invertibilních prvků, tj. (Aut(G),o) je grupa. Příklad 2.51: Popište všechny endomorfismy a automorfismy grupy (Z, +). Určete, čemu je izomorfní monoid End (Z) a grupa Aut (Z). Příklad 2.52: Popište všechny endomorfismy a automorfismy grupy (Z„, +). Určete, čemu je izomorfní monoid End(Z„) a grupa Aut(Z„). 11 Příklad 2.53*: Pro libovolnou dvojici čísel n, k G N popište všechny homoniorfisniy z grupy (Z„, +) do grupy (Zfe,+). Příklad 2.54: Dokažte, že zobrazení / : G —> G definované předpisem f(x) = x^1 je izomorfismus právě tehdy, když grupa G je komutativní. Příklad 2.55: Dokažte, že pro libovolné grupy G a, H jsou grupy G x H a, H x G izomorfní. Příklad 2.56: Uvažme grupu (G, •) matic typu 3 krát 3 nad Z, které jsou v horním trojúhelníkovém tvaru s jedničkami na hlavní diagonále, tj. '1 a b\ G = { \ 0 1 c | a, b, c G v° o V kde • je násobení matic. Definujme nyní zobrazení / : (G, •) —> (Z, +), které matici přiřadí číslo a — c. Dokažte, že zobrazení / je homomorŕismus grup. Příklad 2.57*: Nechť X = {í,..., n}. Ukažte, že grupa (P(X), -=-) z příkladu 1.4-4 je izomorfní grupě (Z??, +)■ ((ZÍJ, +) je součin n kopií grupy (Z2, +).) Příklad 2.58*: Nechť (G, •) je grupa. i) Dokažte, že pro libovolný prvek a G G je zobrazení pa automorŕismus grupy G, kde pa : G —> G je definováno vztahem pa{x) = cixa^1. (Hovoříme o vnitřních automorŕismech.) ii) Ukažte, že množina všech vnitřních automorfismů Inn(G) = {pa \ a G G} je podgrupa grupy (Aut(G), o). iii) Dokažte, že zobrazeni p : G —> Aut (G) dané předpisem p(a) = pa je homomorŕismus grup. Příklad 2.59: Buď a homomorŕismus grupy (Z3o,+) do grupy (Z2o,+) definovaný předpisem a([a]3o) = [6a]2o- Dále nechť /3 je homomorŕismus grupy (Z20, +) do grupy (§5, o) daný předpisem /3([6]2o) = (1, 2, 3, 4, 5)b. Určete jádra homomorfismů a, a P o a. Příklad 2.60: U následujících předpisů (kde a, b G Z, s G Sq) rozhodněte, zda zadávají zobrazení. Pokud ano, rozhodněte, zda se jedná o homomorfismus či dokonce izomorfismus grup. Odpovědi zdůvodněte! 1) a : (Z2, +) x (Z5, +) -> (Z10, +), a(([a]2, [6]5)) = [a + b]w; (3 : (S6, o) -> (§6, o), f3(s) = (1, 2) o s o (1, 2). 2) a : (Z2, +) x (Z5, +) -> (Z10, +), a(([a}2, [b]5)) = [5a + 2b]10; P : (S6, o) -». (§6, o), p{s) = s2. 3) a : (Z4, +) -»■ (C*, •), a([a]4) = «a; /3 : (Z, +) -> (Z3, +), p(a) = [\a\}3. 4) a : (Z5, +) -> (C*, •), a([a]5) = *a; /3 : (Z, +) -> (Z2, +), /3(a) = [\a\]2. Příklad 2.61: U následujících předpisů (kde p, q G Z, q ^ 0 ^ p) rozhodněte zda zadávají zobrazení. Pokud ano, rozhodněte, zda se jedná o homomorfismus či dokonce izomorfismus grup. Odpovědi zdůvodněte! 1) «:(QV)->(QV),«(f) = £, 2) /3:(Q*,.)^(QV),/3(f) = (-ir • £, 3) 7 : (Q*, •) -)■ (Q*, ■), 7(f) = (-1)^+9)9 • l • Příklad 2.62*: Ukažte, že libovolná podgrupa grupy §„, která není podgrupou grupy A„, obsahuje právě polovinu sudých permutací a má tudíž sudý počet prvků. 12 2.6 Konečné komutativní grupy Příklad 2.63: Určete všechny (až na izomorfismus) komutativní grupy, které mají n = 24 prvků. Totéž pro n = 18,24,30,36. Příklad 2.64: Pro libovolnou dvojici přirozených čísel m, n dokažte, že předpis cv([a]m.„) = ([&]„, [a]m) zadává homorŕismus z grupy Zm„ do grupy Z„ x Zm. Rozhodněte, pro která m, n je a izomorfismus. Příklad 2.65: Určete, pro které dvojice čísel m,n jsou grupy Zm„ a Z„ x Zm izomorfní. Příklad 2.66: Určete rozklad grupy (Z^, •) na součin netriviálních cyklických grup. Dejte příklad příslušného izomorfismu. Totéž pro (Zj4, •) a (Z40, •). Příklad 2.67: Dokažte, že grupa, v níž pro každý prvek x platí x ■ x = 1, je komutativní. 2.7 Normální podgrupy Příklad 2.68: Pro libovolné n E N je A„ normální podgrupa grupy §„. Dokažte. Příklad 2.69: Popište všechny normální podgrupy grup (§3, o) a (A4, o). (Povšimněte si, že existuje normální podgrupa N grupy H — normální podgurpy grupy (A4, o) — která není normální podgrupou (A4, o).) Příklad 2.70: Označme následující podgrupy grupy (§6, °): G = {/ G §6 I / sudá} a H = {/ e G | /(3) = 3}, tj. H C G C §6. Rozdodněte, zda a) H je normální podgrupa grupy (G, o); b) H je normální podgrupa grupy (§6, °); c) G je normální podgrupa grupy (§6; °)-Odpovědi zdůvodněte! Příklad 2.71*: Nechť n e N, n > 4. Dokažte, že A„ nemá vlastní normální podgrupy a že je to jediná netriviální normální podgrupa §„. Příklad 2.72: Uvažme grupu (GL2(Q), •) regulárních matic dva krát dva nad racionálními čísly. Buďte dále G, H a N následující množiny matic: Určete, zda se jedná o normální podgrupy grupy (GL2(Q), ■)■ Příklad 2.73: Buď dána následující grupa (G, •) matic ve speciálním tvaru s operací násobení matic a její podgrupa H: Dokažte, že H je podgrupa grupy (G, •). Rozhodněte, zda H je normální podgrupa (G, •). Odpověď zdůvodněte! Příklad 2.74*: Dokažte, že množina vnitřních automorfismů Inn(G) v 2.56 je normální podgrupa grupy všech automorfismů Aut(G). 13 Příklad 2.75: Buď dána grupa (G, o) nekonstantních afinních zobrazení reálných čísel G = {/ : R ->• R I f (x) = ax + b, pro vhodná a G R*, b G R} s operací skládání zobrazení o. Uvažme v této grupě dvě podgrupy: T = {/ : R R | f (x) = ax,ae R*}, S = {/ : R M | /(x) = x + Ď, b G M}. Která z nich je normálni podgrupou grupy (G, o)? Popište u obou pravý i levý rozklad. Příklad 2.76: Popište pravé a levé rozklady grupy §3 podle všech podgrup. Příklad 2.77: Popište levý rozklad grupy (Á4,o) sudých permutací na množině {1,2,3,4} podle podgrupy generované permutací (2,1,4). Příklad 2.78: Určete počet levých tříd grupy (Z, +) x (Z, +) podle podgrupy H = {(m, n) ; 6 | (m — 2n)}. Příklad 2.79: Nechť konečná grupa (G, •) má sudý počet prvků 2n a H je její n prvková podgrupa. Dokažte, že H je normální podgrupa grupy (G, •). 2.8 Faktorizace grup Příklad 2.80: Určete faktorgrupu z příkladu 2.73. Příklad 2.81: Faktorizujte grupu Z podgrupou k% = {ka | a G Z}. Příklad 2.82: Faktorizujte grupu Z„ podgrupou kZn = {kz | z G Z„} = {[/jz]„ | z e Z}, kde k dělí n. Příklad 2.83: Víme, že množina G={(o ľ) Iee{l,-l},ae společně s operací násobení matic tvoří grupu (G, •). Označme podmnožinu G. Ukažte, že iř je normální podgrupa grupy G. Popište rozklad G/H, tj. charakterizujte, kdy dvě matice ^ ^ a ^ ^ ^ náleží 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í a : G —> K pro něž dokažte, že a je surjektivní homomorfismus grup, jehož jádrem je H. Příklad 2.84: Uvažme množiny reálných čísel G = {15p59 | p, q G Z} a H = {3r | r e Z} a operaci • (násobení reálných čísel). Zřejmě (G, •) je grupa. 1. Ukažte, že H je normální podgrupa grupy (G, •). 2. Pro p,p,q,q G Z doplňte podmínku (• • •) tak, aby platilo: 15p59 a 15p59 náleží do stejné třídy rozkladu ^/H ^=> 3. Určete, které grupě je izomorfní faktorgrupa G/H, tj. popište grupu (K, •) a definujte vhodné zobrazení a : G —> K, pro něž dokažte, že a je surjektivní homomorfismus grup, jehož jádrem je H. Řešte stejné zadání pro množinu Hi = {45r | r e Z} a H2 = {25r27s | r, s G Z}. 14 Příklad 2.85: Uvažme množiny reálných čísel G = {2p3q5r | p, q, r e Z} a H = {20x \ x e Z} a operaci • (násobení reálných čísel). Zřejmě (G, •) je grupa. 1. Ukažte, že H je normální podgrupa grupy (G, •). 2. Pro p,p, q,q,r,ř E Z doplňte podmínku (• • •) tak, aby platilo: 2p3«5r a 2P.3«5~ náleží do stejné třídy rozkladu G/H 3. Určete, které grupě je izomorfní faktorgrupa G/H, tj. popište grupu (K, •) a definujte vhodné zobrazení a : G —> K, pro něž dokažte, že a je surjektivní homomorfismus grup, jehož jádrem je H. Řešte stejné zadání pro množinu H = {8xl5y \ x,y £ Z}. Příklad 2.86: Faktorizujte aditivní grupu komplexních čísel podgrupou všech reálných čísel. ((C, +)/K =?) Příklad 2.87: Určete, čemu je izomorfní faktorgrupa regulárních matic nad reálnými čísly podle podgrupy matic jejichž determinant je roven 1. (GL„(M)/SL„(IR) =?) Příklad 2.88: Nechť je dána grupa matic G={(l °) \a,ce®*,bt< s operací násobení. Dokažte, že podgrupa H={(l c) KMeQ,a,c>0 je normální a určete faktorgrupu. Příklad 2.89: Uvažujme normální podgrupu grupy (G, +) = (Z, +) x (Z, +) definovanou takto: (a) : H = {(a, b) e Z x Z; 5 | a, 2 | 6}, (b) : H = {(«, b) e Z x Z; 7 | 2a + 36}, Určete, které grupě je izomorfní faktorgrupa G/H, tj. popište grupu (K, •) a definujte vhodné zobrazení a : G —> /í, pro něž dokažte, že a je surjektivní homomorfismus grup, jehož jádrem je H. Příklad 2.90*: V příkladu 2.67 jsme spočítali jednu netriviální normální podgrupu v §4 resp. A4, označme ji V4. Spočtete příslušné faktorgrupy. (§4/V4 =?, A4/V4 =?) Příklad 2.91*: Dokažte, že až na izomorfismus existují pouze dvě 2p prvkové grupy a popište je. (Zde p je prvočíslo.) Příklad 2.92*: Určete faktorgrupy z příkladu 2.70. 2.9 Doplňující příklady z teorie grup Příklad 2.93*: i) Ukažte, že libovolný automorfismu grupy §„ zachovává paritu permutace. ii) Dokažte, že pro n > 2 je grupa vnitřních automorfismu Inn(§„) izomorfní grupě §„. iii) Dokažte, že Aut(§„) = §„ pro n = 3,4, 5. 15 Příklad 2.94*: Buď (G, •) komutativní grupa. Ukažte, že pro dané n e N tvoří množina Gn = {a G G | an = 1} podgrupu grupy (G, •). Ukažte dále, že množina všech prvků konečného řádu G = U^Li Gn = {a G G \ 3n G N : an = 1} je taktéž podgrupou grupy (G, •). Příklad 2.95*: Nechť je dána grupa G a její dvě podgrupy H a K. Definujme nyní podmnožinu HK grupy G: HK = {hk \ h £ H, ke K}. Dokažte, že pokud je K normální podgrupa grupy G, potom je podmnožina HK podgrupou grupy G. Dále dokažte, že pokud jsou obě podgrupy H i K normální, potom je normální i podgrupa HK. Příklad 2.96*: Nechť (G, •) je grupa, n G N a předpokládejme, že grupa G obsahuje jedinný prvek řádu n (označme jej a). Dokažte, že tento prvek komutuje s libovolným prvkem grupy G, tj. xa = ax pro libovolné x G G. Příklad 2.97*: Nechť G je grupa a označme G' podgrupu generovanou množinou prvků tvaru [x,y] = x~xy~xxy, tj. G' = {[xi,yi][x2,y2] ■ ■ ■ [xn,yn} | n G N,xuyt G G}. i) Dokažte, že G' je normální podgrupa grupy G. ii) Ukažte, že faktorgrupa G/G' je komutativní grupa. iii) Ukažte, že G/G' je „největší" komutativní faktorgrupa grupy G, tj. ukažte, že pokud H je normální podgrupa grupy G taková, že G/H je komutativní grupa, potom G' C H. iv) Určete „největší" komutativní faktorgrupu pro grupu G = {(o c) lfl'c£^6e4 Totéž pro GL2(Q). Příklad 2.98*: i) Nechť (G, •) a (H,*) jsou grupy a nechť ip : (H,*) —> (Aut(G), o) je homomorfismus grup. Definujme na G x H operaci o vztahem: (a, b) o (c, ď) = (a ■ (p(b)(c), b*ď). Dokažte, že (G x H, o) je grupa. ii) Ukažte, že součin grup (G, •) x (H, *) je speciálním případem (G x H, o) pro vhodné ip. iii) Nechť (G, •) je grupa. Definujme na G x G operaci o vztahem: (a, b) o (c,ď) = (abcb^1, bď). Dokažte, že (G x G, o) je grupa. Příklad 2.99*: Ukažte, že libovolná konečná grupa je izomorfní s podgrupou grupy A„ pro vhodné n G N. 3 Polynomy nad Z, Q, M a C 3.1 Dělení v okruzích polynomů, Euklidův aloritmus, Bezoutova rovnost Příklad 3.1: VQ[i] dělte se zbytkem polynomy a) (x5 + x3 - 2x + 1) : (-x3 + x + 1), b) (3x3 + ÍOx2 + 2x - 3) : (5x2 + 25x + 30), c) (Í2x4 + 3x3 - Ax + 3) : (2x2 - 1), d) (xe + x4 + x2 + 1) : (x2 - x + 1). 16 Příklad 3.2: V Q[x] dělte se zbytkem polynomy: a) (2x3 + 3x2 - Ax + 5) : (x - 2), b) (Ax4 - 3x2 - x + 2) : (3 x + 1). Příklad 3.3: Nalezněte polynomy f(x),g(x) G Q[x], které jsou stupně 3, každý z nich má alespoň jeden alespoň dvojnásobný kořen a jejich největší společný dělitel je: a) x2 + x — 6, b) x2 + x - 2, c) x2 + 2x - 3. Vyjádřete největší společný dělitel polynomů /, g Bezoutovou rovností. Příklad 3.4: Nalezněte polynomy f(x),g(x) G Q[x], které jsou stupně 4, každý z nich má alespoň jeden alespoň trojnásobný kořen a jejich největší společný dělitel je: a) x2 + x — 2, b) x2 + 2x - 3, c) x2 - 2x - 3. Vyjádřete největší společný dělitel polynomů f,g Bezoutovou rovností. Příklad 3.5: Pro dané dvojice polynomů /, g G M.[x] najděte normovaný polynom, který je jejich největším společným dělitelem. Najděte koeficienty do příslušné Bezoutovy rovnosti. a) f = x4 + l,g = x3 -1 b) / = x4 + 3x3 - x2 - Ax - 3, g = 3x3 + ÍOx2 + 2x - 3 c) / = x5 - 5x4 + Ax3 + 8x2 - 8x - 3, g = xA - 2x3 - 7x2 + 8x + 3 3.2 Kořeny polynomů Příklad 3.6: Uvažme polynom f(x) = x6 — 6x5 + 9x4 + 8x3 — 2Ax2 + 16 G Q[x]. Dokažte, že c = 2 je kořenem polynomu / a určete jeho násobnost n. Příklad 3.7: Určete hodnotu koeficientu a G Q tak, aby polynom / = x5—ax2 — ax+l G Q[x] měl dvojnásobný kořen c = — 1. Příklad 3.8: Dokažte, že pro každé n G N je c = 1 dvojnásobným kořenem polynomu nxn+1 — (n+ \)xn + 1 G Z[x]. 3.3 Taylorův rozvoj polynomu Příklad 3.9: Vyjádřete polynom f(x) = x4 + 2x3 — 3x2 — Ax + 1 v mocninách lineárního polynomu x + 1. Příklad 3.10: Vyjádřete polynom f(x) = (x - 2)4 + A(x - 2)3 + 6(x - 2)2 + 10(x - 2) + 20 bez počítání jednotlivých mocnin polynomu x — 2. 3.4 Racionální kořeny polynomů Příklad 3.11: Nalezněte všechny racionální kořeny polynomu v C[x] a určete jejich násobnost. a) 12xe + 8x5 - 85x4 + 15x3 + 55x2 + x - 6 b) Ax7 - Wx6 + x5 + 55x4 - 35x3 - 38x2 + 12x + 8 c) Ax7 - 23x5 + 17x4 + 31x3 - A9x2 + 2Ax-A d) 2x7 - 3xe - 20x5 -x4 + 66x3 + 91x2 + A8x + 9 e) Ax5 + 8x4 - 27x3 - 79x2 - 56x - 12 f) Ax5 - 35x3 + 15x2 + AOx + 12 g) x3 - %x2 - \x + \ h) 5x3 - 8x2 + llx + 6 i) 12x4 - 7x3 - 19x2 - 3x + 2 17 3lĽ X I 3^ I k) 6x4 + x3 + x2- 16x - 12 1) 9x6 - 21x5 - 17x4 + 15x3 - 42x2 - 34x - 6 m) 4x6 - 12x5 + 9x4 - 12x2 + 36x - 27 n) 2x7 - 3x6 - 8x5 + 6x4 + ÍOx3 + x2 + Ax + 4 o) x4 + x3 - 2x2 - 3x - 1 p) x5 - Ax4 + Ax3 + 2x2 - 5x + 2 q) f = I2x7 - 56x6 + 115x5 - 141x4 + 103x3 - 35x2 - 3x + 9 r) g = 8x7 - 44x6 + 70x5 - 17x4 - 24x3 + 10x2 + 2x - 1 Příklad 3.12: Určete takové a G C, pro něž má polynom / = 2x6 - x5 - llx4 - x3 + ax2 + 2ax + 8 £ C [x] kořen 2. Pro toto a určete všechny racionální kořeny polynomu / včetně násobností. Příklad 3.13: Určete všechna a G Z, pro něž má polynom x4 + 2x3 — 3x2 + ax — 4 racionální kořen. 3.5 Komplexní kořeny polynomů Příklad 3.14: Určete všechna komplexní řešení rovnice x" = 2 pro n e N. Příklad 3.15: Nalezněte rovnici, jejíž všechna komplexní řešení tvoří v Gaussově rovině rovnostranný trojúhelník se středem v nule a jedním vrcholem v i. Příklad 3.16: Řešte v C kvadratickou rovnici x2 + (1 + 3í)x + i — 2 = 0. Příklad 3.17: Určete všechna komplexní řešení rovnice x4 + x3 + x2 + x + 1 = 0. 3.6 Rozklad polynomů Příklad 3.18: Napište rozklad polynomu na součin ireducibilních faktorů postupně nad Q, M, C: b) 5x3 -8x2 +2llx+ 6 c) 12x4 - 7x3 - Í9x2 - 3x + 2 3ízľ x | 77 x 77 x I 77 x e) 6x4 + x3 +x2 - 16x - 12 f) 4x6 - 12x5 + 9x4 - Í2x2 + 36x - 27 g) 9x6 - 21x5 - Í7x4 + 15x3 - A2x2 - 34x - 6 Příklad 3.19: Napište rozklady na součin ireducibilních polynomů postupně nad C,R, Q těch polynomů z Příkladu 3.11, u kterých znáte dostatek racionálních kořenů. Příklad 3.20: Určete všechny kořeny polynomu /, víte-li, že má tři kořeny racionální. Rozložte / na ireduci-bilní faktory postupně nad Q, R, C: a) f(x) = Ax5 - Ax4 - 5x3 - 7x2 + x + 2 e C [x], b) f (x) = Ax5 - Í2x4 - 13x3 - 13x2 + 3x + 4 e C [x]. 3.7 Komplexně sdružené kořeny Příklad 3.21: Určete všechny kořeny polynomu / = x' - 4x6 + 8x5 — 7x4 + 8x2 — 8x + 4 e C [x], víte-li, že má dvojnásobný kořen 1 + i. Rozložte tento polynom na ireducibilní faktory postupně nad Q, R, C. Příklad 3.22: Mezi všemi normovanými polynomy s reálnými koeficienty, které mají jednoduchý kořen — | a dvojnásobný kořen 3 + 2i, nalezněte polynom nejmenšího stupně. Rozložte tento polynom na ireducibilní polynomy nad Q, R, C. 18 Příklad 3.23: Určete všechny kořeny polynomu / = x6 - 7x5 + 20x4 - 30x3 + 37x2 - 55x + 50 g C [x], víte-li, že má dvojnásobný kořen 2 — i. Rozložte jej na ireducibilní faktory postupně nad Q, M, C. Příklad 3.24: Mezi všemi normovanými polynomy s reálnými koeficienty, které mají dvojnásobný kořen ^ a dvojnásobný kořen k nalezněte polynom nejmenšího stupně. Zapište rozklad tohoto polynomu na ireducibilní faktory postupně nad Q, R, C: Příklad 3.25: Nalezněte všechny kořeny polynomu x4 + 4x2 + x + 6 g C [x] a určete jejich násobnost, víte-li, že jedním z kořenů je číslo ~1+21^. Příklad 3.26: Víme, že polynom / = 4x6 — 4x5 + 4x4 — 4x3 + 5x2 — 3x + 1 g C [x] má dvojnásobný kořen \ + \i. Určete zbývající kořeny polynomu /. Příklad 3.27: Uveďte příklad polynomu v R[x], resp. v Z[x], jehož kořenem je a) 1 + b) 2 + y/3i, c) VŠ — 5í. 3.8 Eisensteinovo kritérium a ireducibilita nad Q Příklad 3.28: Ukažte, že polynom f(x) je ireducibilní nad Q: a) f(x) = xn + p; n E N, p je prvočíslo, b) f(x) = xe +x3 + 1. Příklad 3.29: Najděte n e N takové, že polynom a'2 — n je ireducibilní nad Q, ale nesplňuje podmínku Eisensteinova kritéria. Příklad 3.30: Najděte n £ N tak, aby polynom p(x) = xn + n a) byl ireducibilní nad Q, b) nebyl ireducibilní nad Q. Příklad 3.31: Určete, který z polynomů f(x) = x5 + 3x3 - 9x + 3 g Z [x] a g(x) = x4 + 4x3 + 5x2 — 3 g Z [x] je ireducibilní nad Z a který lze nad Z rozložit na součin polynomů nižšího stupně. Napište rozklady polynomů / a g na ireducibilní faktory nad Z. Příklad 3.32: Dokažte, že polynom x4 + x3 + x2 + x+ 1 je ireducibilní nad Q. Návod: Použijte Taylorův rozvoj ve vhodném bodě. Příklad 3.33: Dokažte, že polynom x4 + x + 1 je ireducibilní nad Q. Návod: Použijte metodu neurčitých koeficientů. 3.9 Minimální polynom Příklad 3.34: Určete minimální polynomy prvku \/2 + \p2 nad Q a nad Q(a/2). Příklad 3.35: Určete minimální polynomy prvků nad Q: a) k = 1 — i, b) k = 1 - li. a Příklad 3.36: Určete minimální polynom prvku \fl + 4-\/3 nad Q. 19 Příklad 3.37: Určete minimální polynom prvku \/16 + 8y/E nad Q. Příklad 3.38: Určete minimální polynom prvku cos -y- + z sin -f- = £3 nad Q- Příklad 3.39: Určete minimální polynomy prvků nad Q: o;=v/3-l, P = V2 + VŠ+V6, -/ = V2i+\^2i, ó = VŤí. 4 Okruhy a tělesa 4.1 Okruh, podokruh Příklad 4.1: Rozhodněte, zda (M, ©, 0) je okruh: a) M = 1x Q) y = x + y — í,x Q y = x ■ y — 1 b) M = Z,x(By = x + y — 1, xQy = x + y — xy c) M = Q, operace jako v b) d) M = Q x Q, (x, y) (b (u, r) = (x + m, y + v), {x, y) O (m, v) = (xu + 2yv, xv + y u) e) M = Z2 x Z2, (x, y) (S (u, r) = (x + m, y + t;), (x, y) Q (ií, v) = (xu + yv, xv + yu + yv) Příklad 4.2: Necht (R, +, •) je komutativní okruh. Rozhodněte, zda je okruh také a) (R, + , □), kde □ je operace definovaná vztahem adb = a- b + b- a pro libovolné a, b G R, b) (R,+,+). Příklad 4.3: Rozhodněte, zda daná množina M je podokruhem okruhu (C, +, •): a) M = {a + 2i \ a G M}, b) M = {a + 2i | a G C}, e) M = {a + bi\aeR,b e N}, d) M = {3a+bi | a G Z, Ď G Z}, e) M = {ft + 26?- | o G Z, 6 G Z}, f) M = {^r | a G Z, A- G N}. Příklad 4.4: Rozhodněte, zda daná podmnožina A okruhu racionálních čísel (Q, +, •) je okruh, případně obor integrity. Jde-li o okruh, charakterizujte jeho invertibilní prvky. aM = {f |pGZ,gGN,3|g} b) A = {§; | m G Z, n G N} c) 4 = {f |meZ,n€N} Příklad 4.5: Určete, které prvky náleží nejmenšímu podokruhu okruhu (C, +, •) obsahujícímu číslo a pro a) a = VŠ, b) a = n, c) a = i, d) a = cos ^ - f í sin ^ e) a = cos ^j- H h í sin ?f = b, f) a = g) a = y/ň, h) a = y/ň, i) a = Jňi. 20 4.2 Homomorfismy okruhů Příklad 4.6: Rozhodněte, zda zobrazení / : C —>• C je homomorfismus okruhu (C, +, •) do okruhu (C, +, •), je-li pro a, b G R dáno: a) f(a + 6 i) = a + b, b) J(a + fo) = a2 + Ď2, c) f (a + bi) = a — bi. Příklad 4.7: Určete, zda je okruh (Z2, +, •) x (Z3, +, •) oborem integrity. Je izomorfní s okruhem (Z$, +, •)? Příklad 4.8: Dokažte, že okruh (Z, ®, 0) z příkladu 4.1 b) je izomorfní s okruhem (Z, +, •). Příklad 4.9: Určete všechny čtveřice (a, b, c, d) G R4 takové, že předpis a(r + s i) = (ar + bs) + (cr + ds) i, pro r, s G R, definuje homomorfismus a : C —> C okruhu C do sebe. Pro které z nich se jedná o izomorfismus? Příklad 4.10: Buď Q(y/Š) = {a + by/Š | a, 6 G Q} podokruh okruhu (R, +, •). Dokažte, že libovolný okruhový homomorfismus a : Q (-v/3) ^ C je identický na množině racionálních čísel, tj. Vr G Q : a (r) = r. Popište všechny okruhové homomorfismy a : Q (-v/3) C Které z nich jsou izomorfismy? 4.3 Obory integrity, invertibilní prvky okuhů, tělesa Příklad 4.11: Rozhodněte, zda následující podmnožina M okruhu komplexních čísel (C, +, •) je okruh, obor integrity, případně těleso. Jde-li o okruh, charakterizujte jeho invertibilní prvky. a) M = {a + bi \ a, b G Z} b) M = {a + b ■ y/E I a, 6 G Q} c) M = {a + b ■ y/E I a, b G Q} d) M = {a + b ■ I a, Ď G Q} Příklad 4.12: Nalezněte invertibilní prvky okruhu ({a + b ■ !±ySí \ a,b e Z}, +, •) Příklad 4.13: Pro okruhy v příkladech 4.1 a 4.4 rozhodněte, zda se jedná o obor integrity a těleso. V okruzích, které nejsou tělesem, charakterizujte invertibilní prvky. Dále rozhodněte, zda invertibilní prvky tvoří podokruh. Příklad 4.14: Pro prvky z příkladu 4.5 najděte nejmenší podtěleso tělesa (C, +, •) obsahující daný prvek. 4.4 Polynomy nad Zp Příklad 4.15: Nalezněte všechny kořeny polynomu x5 + 5x4 — x2 — x + 3 v Z7. Příklad 4.16: Určete všechny ireducibilní polynomy nad a) Z2 stupně menšího než 5, b) Z3 stupně menšího než 4. Příklad 4.17: S využitím příkladu 4.16a) dokažte, že polynomy x4 + x3 + x2 + x + 1, x4 + x3 + x2 + x + 3 a x4 + x3 — x2 + x + 1 jsou ireducibilní nad Z. Příklad 4.18: Nalezněte všechny kořeny polynomu x6 — x5 — x4 — x3 — x2 — x + 1 E Z$[x] v Z$[x] a určete jejich násobnost. Příklad 4.19: Určete nějaký prvek a G Z5 takový, že polynom x3 + x2 + ax + 1 je ireducibilní nad Z5. Příklad 4.20: Určete všechny prvky a G Z7, pro které je polynom x3 + x2 + x + a ireducibilní nad Z7. 21 Příklad 4.21: Metodou neurčitých koeficientů rozhodněte, zda je polynom x4 + x3 + x2 + x + 2 ireducibilní nad Z5. Totéž pro polynom x4 + x3 + 3x + 1. Příklad 4.22: Udejte příklad polynomu a) g g ^[x], který je stupně 5, má dvojnásobný kořen 2 a žádné jiné kořeny nemá, b) g g Z2[:r], který je stupně 5, není ireducibilní a nemá žádný kořen, c) g g 7L-i\x\, který je stupně 4, není ireducibilní a nemá žádný kořen, d) g g 7L-i\x\, který je stupně 5, není ireducibilní a nemá žádný kořen, e) g g Zs[x], který je stupně 6, má dvojnásobný kořen 2, jednoduchý kořen 4 a který nemá žádné další kořeny. Příklad 4.23: Rozložte polynomy na ireducibilní faktory. a) x6 + x5 + x2 + 1 g Z2 [x] b) x7 + 3xe + 2x5 - x4 + 3x3 - x2 + x + 1 g Z5[x] c) x5 + x4 + x3 + x2 + x + 1 g Z2 [x] d) x7 - x6 + 2x4 + x3 - x2 + 2 g Z5[x] e) x5 + x4 + x3 - x2 + 1 g Z3 [x] f) x4 +x3 +x + 1 g Z2[x] g) x5 + 3x3 + x + 3 g Z5[x] h) x5 + x3 + 2x2 + 2 Příklad 4.24: Pro následující polynomy /, g g Zs[x] najděte normovaný polynom, který je jejich největším společným dělitelem. Najděte koeficienty do příslušné Bezoutovy rovnosti: a) / = x3 + x2 + x + 1, g = x2 + 2x + 2; b) / = x3 + x2 + x, g = x2 + 2x + 2; c) / = x4 + x2 + 1, g = x3 + x2 + x + 1. Příklad 4.25: Uvažujme okruh polynomů 7hä\x\. Zdůrazněme nejdříve, že uvažované polynomy v tomto příkladu nejsou polynomy nad tělesem, ale polynomy nad okruhem Z4, který není obor integrity. a) Popište jednotky okruhu 7h^x\. b) Určete všechny prvky dělící prvek 2 g Z4 [x]. c) Ukažte, že x j( x + 2 a, x + 2 j(x. d) Dokažte, že 2 • x = 2 ■ (x + 2) jsou různé rozklady téhož prvku na ireducibilní prvky. e) Dokažte, že prvky 2 • x a x(x + 2) nemají v Z4[x] nej většího společného dělitele. Poznámka: v příkladu jde s úspěchem využít následujících dvou faktů. 1) Pro nenulový polynom / je jeho stupeň o jedna menší než stupeň polynomu x ■ f. 2) Přirozené zobrazení Z4[x] —> Z2[a;] je homomorfismus okruhů, které jednotky zobrazuje na jednotky. Pokud tato nápověda nestačí, podívejte se na řešení do skript do odstavce 5.19. 4.5 Ideály a faktorokruhy Příklad 4.26: Určete podgrupu grupy (C, +) generovanou prvkem i. Určete podokruh, podtěleso a ideál okruhu (C, +, •) generovaný prvkem i. Totéž pro prvky \J~2 a e. Příklad 4.27: Popište všechny ideály okruhu Z2 x Z4. Příklad 4.28: Ukažte, že ideál (x, 2) není hlavní ideál okruhu Z[x]. Příklad 4.29: Určete všechny ideály v okruhu Maí2(M) (okruh matic typu 2x2 nad reálnými čísly). Příklad 4.30: Pro okruh R a jeho ideály /, J klademe I + J = {í + j | i g I,j g J}. Dokažte, že n i + jsou operace na množině všech ideálů okruhu R. 22 Příklad 4.31: Pro okruh R a jeho ideály /, J klademe I o J = {í ■ j | í g /, j g J}. Rozhodněte, zda o je operace na množině všech ideálů okruhu R. Příklad 4.32: Dokažte, že v okruhu Zn je každý ideál hlavní. Příklad 4.33: Určete ideál generovaný prvkem \/2 v okruhu Z[V2] = {a + b^/2 \ a, b g Z}. Čemu je izomorfní příslušný faktorokruh? Příklad 4.34*: Určete, pro která n g N je v okruhu Zn[x] každý ideál hlavní. Příklad 4.35*: Dokažte, že každý ideál okruhu Z[x] je konečně generovaný. Příklad 4.36: Dokažte, že množina všech polynomů, které mají součet koeficintů dělitelný 3, tvoří v okruhu Z[x] ideál. Rozhodněte, zda se jedná o hlavní ideál. Určete, čemu je izomorfní příslušný faktorokruh. Příklad 4.37: Dokažte, že množina všech polynomů, které mají všechny koeficinety sudé, tvoří v okruhu Z[x] ideál. Určete, čemu je izomorfní příslušný faktorokruh. Příklad 4.38: Pro dané přirozené číslo n a celé číslo k označme I(k,n) = {/ g Z[x] | n | f(k)}. Dokažte, že I(k, n) je ideál okruhu Z[x]. Rozhodněte, pro která n, k je tento ideál hlavní, pro která je maximální, pro která je to prvoideál. Nalezněte generátory tohoto ideálu. Příklad 4.39: Určete, čemu je izomorfní faktorokruh Q[x]/(x — 2). Příklad 4.40: Určete, čemu jsou izomorfní faktorokruhy a) Q[x,y]/(x,y), b) Q[x,y]/(x,y-l), c) Q[x, y]/(x), d) Q[x, y]/I, kde I={fe Q[x, y] \ f(x, x) = 0}. Příklad 4.41: Určete, čemu je izomorfní faktorokruh R[x]/(x2 + 1). Příklad 4.42: Ukažte, že faktorokruh Q[x, y\j(x2, y2) je izomorfní okruhu čtvercových matic: Id 0 0 0\ c d 0 0 b 0 d 0 \ji b c d J a, b, c, d g Příklad 4.43: Označme pro prvočíslo p okruh Mp = | m, n g Z, p \ n|. Popište všechny ideály tohoto okruhu. Určete, které z nich jsou hlavní, které prvoideály a které maximální ideály. Příklad 4.44*: Určete, čemu jsou izomorfní faktorokruhy příslušné ideálům z příkladu 4.43. Příklad 4.45: Určete faktorokruh Z[x]/I(k,n) z příkladu 4.38. 4.6 Jednoduchá rozšíření Příklad 4.46: Určete, které prvky patří do tělesa Q(i), Q(v2 + y/2). Určete stupně příslušných rozšíření (nad 23 Příklad 4.47: Buď a e C kořenem (ireducibilního) polynomu x3 — x — 2 G Q [x]. Určete stupeň rozšíření telesa Q(a) nad tělesem Q a udejte bázi tohoto rozšíření. Vyjádřete prvky a^1, (1 + a)3 v této bázi. Příklad 4.48: Určete, které prvky patří do tělesa Q(tt). Příklad 4.49: Určete všechny inkluze mezi následujícími podtělesy tělesa C: Q ,-v/3), Q(V%, v/6), Q(*\/3, Vš), Q(*\/2, V3, VŠ)- Určete stupně rozšíření těchto těles nad Q. Jsou tělesa a Q(\/3) izomorfní? Příklad 4.50: Určete, které prvky patří do tělesa Q (-v/2, v7^)- Určete stupeň rozšíření nad tělesem Q a rozhodněte, zda se jedná o jednoduché rozšíření. Příklad 4.51*: Dokažte, že je v okruhu Z„[x] každý ideál hlavní právě tehdy, když n není dělitelné druhou mocninou prvočísla. Postupně dokažte, že: • Pokud existuje prvočíslo p takové, že p2 | n, pak ideál (x,p) není hlavní ideál v Z„[x]. • Pokud n je prvočíslo, pak Z„[x] je okruhem hlavních ideálu. • Pokud n je součinem různých prvočísel p\, p2,. .. , Pk, pak okruh Z„ [x] je izomorfní součinu okruhů ZPl [x], ZP2 [x], ... ,ZPfc [x]. • Každý ideál I v konečném součinu okruhů je součinem příslušných ideálů v jednotlivých komponentách součinu. Pokud jsou navíc tyto ideály hlavní, je hlavní i původní ideál I. 4.7 Konečná rozšíření a rozkladové těleso Příklad 4.52: Ukažte, že tělesa Q (-v/2) a Q(-\A3) nejsou izomorfní. Příklad 4.53: Je-li ip : Q(a) —> Q(/3) izomorfismus, pak ip(a) má stejný minimální polynom jako a. Dokažte. Příklad 4.54: Dokažte, že Q (-v/2, V$) je jednoduché rozšíření Q. Určete stupeň tohoto rozšíření. Příklad 4.55: Určete všechny automorfismy (izomorfismy na sebe) tělesa Q(y/2). Příklad 4.56: Určete stupeň rozšíření rozkladového tělesa polynomu x4 — 2 nad Q. Příklad 4.57: Určete stupeň rozšíření rozkladového tělesa polynomu x3 — 2 nad Q. Příklad 4.58: Určete stupeň rozšíření rozkladového tělesa polynomu xn — 1 nad Q, pro n = 3,4, 5, 6. Příklad 4.59: Určete stupeň rozšíření rozkladového tělesa polynomu xn — 1 nad Q, pro n prvočíslo. Příklad 4.60: Dokažte, že pro polynom stupně n nad Q, je stupeň rozkladového tělesa tohoto polynomu menší nebo roven n\. Příklad 4.61: Uvažujme ireducibilní polynom / = x3 + x +1 nad Z2. Popište těleso Z2[x]/(/). Určete všechny jeho podtělesa. Příklad 4.62: Určete všechny automorfismy tělesa Q(v/2, V/3)- Příklad 4.63: Určete stupeň rozšíření rozkladového tělesa polynomu x3 — 5 nad Q. 24 Příklad 4.64: Uvažujme ireducibilní polynom / stupně 4 nad Z2. Popište těleso Z2[2ľ]/(/). Určete všechny jeho podtělesa. Příklad 4.65*: Popište všechna konečná rozšíření tělesa C. 4.8 Konečná tělesa, grupy automorfismů Příklad 4.66: Uvažujme šestnáctiprvkové těleso Fi6- Buď /3 generátor jeho čtyřprvkového podtělesa. a) Určete minimální polynom prvku /3 nad Z2. Napište jeho rozklad na ireducibilní polynomy nad Z2 . b) Určete všechny ireducibilní polynomy stupně 2 nad Z2(/3). c) Nechť / je nějaký ireducibilní polynom stupně 2 nad Z2(/3). Nalezněte jeho kořeny v Fi6- Popište izomorfizmus Fi6 a Z2(/3)[x]/(f). Příklad 4.67: Uvažujme těleso Fpn o pn prvcích a jeho grupu automorfismů (Aut(¥p-n.),o). Nechť zobrazení l : Fpn —> Fpn je definováno vztahem l(x) = xp. a) Dokažte, že l je automorfismus tělesa ¥pn. b) Ukažte, že l je prvek řádu n v grupě (Aut(¥pn)1 o). c) Ukažte, že ¥pn je jednoduché rozšíření tělesa ¥p = Zp a proto existuje právě n automorfismů ¥pn. tzn. (Aut(¥pn), o) je n prvková cyklická grupa. Příklad 4.68: Popište, kolik je homomorfismů z ¥pn do ¥qm a jak vypadají. Příklad 4.69: Určete grupu automorfismů rozkladového tělesa polynomu x5 — 1 nad Q. Příklad 4.70: Pro některou dvojici /, g různých ireducibilních polynomů stupně 2 nad Z3 popište všechny homomorfismy z Zs[x]/(f) do Z^[x]/(g). Příklad 4.71*: Určete grupu automorfismů rozkladového tělesa polynomu x4 — 2 nad Q. 4.9 Počítání v jednoduchých rozšířeních těles Příklad 4.72: Buď e e C kořen polynomu f = x3 — x — 2 E Q[x]. Dokažte, že / je ireducibilní polynom. Vyjádřete prvky e-1 , (1 + e)3 a (e2 + 3e — 1)~2 ve tvaru ciq + a\ ■ e + a2 • e2, kde ag, a±, a2 G Q. Příklad 4.73: Buď e e C kořen polynomu / = x4+ 2x2 - 4x + 2 e Q [x]. Vyjádřete čísla e-1, e6 a (e2 + e+l)_1 ve tvaru ao + &i • e + a2 • e2 + c13 ■ e3, kde at e Q pro z = 0,. .. , 3. Příklad 4.74: Označme a = \/3i + -y/Š- Dokažte, že Q(a) = Q(-\/3i). Vyjádřete komplexní číslo ^ bez použití jiných než racionálních čísel ve jmenovateli. Příklad 4.75: Buď f = x2 + [1]^ e Z^x]. Dokažte, že Fg = Z^[x]/(f) je 9-prvkové těleso. Označme a e Fg prvek a = x + (/). Určete 1 e Z takové, že i) [a-oh + [a-ih -a = a4; ii) [aoh + m3 - a= (a+ [1]3)_1- Příklad 4.76: Buď / = x4 + x3 + 1 e Z2[x] a označme Fi6 = Z2[x]/(/) příslušné těleso. Označme a e Fi6 prvek a = x + (/). Určete G Z2 pro i = 0,1, 2, 3 takové, že i) ao + &i • a + • • • + íx3 • a3 = a6; ii) ap + &i • a + • • • + íx3 • a3 = (a2 + 25 Příklad 4.77: Buď f = x3 - x + [2]5 g Z5[x] a nechť F125 = Z5[x}/(f) je 125-prvkové těleso. Označme a e F125 prvek a = x + (/). Určete a, 6, c e Z taková, že i) N5 + [bh ■ a + ' a2 = a5, n) [a]5 + [b}5 ■ a + [c]5 • a2 = (a4 + a + l)-1. 26