MIN401 Matematika IV - příklady počítané na cvičení (jarní semestr 2021) 1   1. týden — dělitelnost
Cvičení konané 3. 3. 2021.
Příklad 1.1:   [10.2] Dokážte, že pro libovolné a G Z platí:
(i) a2 dává po dělení čtyřmi zbytek 0 nebo 1,
(ii) a2 dává po dělení osmi zbytek 0, 1 nebo 4,
(iii) a4 dává po dělení šestnácti zbytek 0 nebo 1.
Příklad 1.2:
(i) Ukažte, že pro každé n G N platí 3|4n — 1.
(ii) Ukažte, že pro každé n G N platí 5 [n5 — n.
(iii) Ukažte, že pro každé n G N platí 5|33n+1 + 2n+1.
Příklad 1.3: [10.1] Určete, pro která přirozená čísla n G N je číslo n3 + 1 dělitelné číslem n — 1.
Příklad 1.4: [10.4 a 10.5] Určete největší společný dělitel čísel a, b G Z a určete příslušné koeficienty v Bezoutově rovnosti:
(i) a = 10175 a 6 = 2277,
(ii) a = 249 - 1 a 6 = 235 - 1.
Příklad 1.5:
(i) Nechť a, b G N, a ^ b. Ukažte, že existuje nekonečně mnoho přirozených čísel n takových, že čísla a + n a b + n jsou nesoudělná.
(ii) Nechť má číslo n G N, n > 1 následující vlastnost: pro každou dvojici dělitelů a > 1, 6 > 1 čísla n platí, že (a, b) > 1. Co můžeme říci o číslu n?
Příklad 1.6: [10.10]
(i) Dokažte, že jsou-li čísla m, n G N nesoudělná, jsou nesoudělná i čísla
m2 + mn + n2   a   m2 — mn + n2.
(ii) Dokažte, že jsou-li lichá čísla m, n G N nesoudělná, jsou nesoudělná i čísla
m + 2n   a   m2 + An2.
2   2. týden — kongruence, Eulerova funkce
Cvičení konané 10. 3. 2021.
Příklad 2.1: [10.11])
(i (ii
Příklad 2.2:   [10.15 a 10.16]
(i (ii (iii
Příklad 2.3:   [10.17] Pro číslo n G N označuje 15(72) ciferný součet čísla n.
(i (ii
(iii
(iv
(i (ii
(iii
(iv
(v
Nalezněte zbytek po dělení čísla 7   číslem 50. Určete poslední dvě cifry dekadického zápisu čísla 730.
Nechť m,nGNao,i£Z splňují a = b (mod mn). Ukažte, že pak am = bm (mod mn+1)
Ukažte, že lichá čísla a splňují a4 = 1 (mod 16).
Ukažte, že čísla a nedělitelná třemi splňují a3 = ±1 (mod 9).
Zopakujte si pravidla po dělitelnost 2, 3, 4, 5, 6, 8, 9. Ukažte, že n = S (n) (mod 9). Pravidlo pro dělitelnost 11.
Ukažte, že pro n = 1000a + b platí n = —a + b (mod m), kde m G {7,11,13}.
Příklad 2.4:   [10.19, 10.20, 10.21]
Určete <p(72).
Dokažte, že pro každé nGN platí <p(Ari + 2) = íp(2n + 1) Určete všechna nGN taková, že íp(ri) je liché. Určete všechna nGN taková, že íp(ri) = 30. Určete všechna nGN taková, že íp(ri) = |.
Příklad 2.5:   [10.24, 10.26, 10.28, 10.29]
(i) Určete poslední dvojčíslí čísla. 72013.
(ii) Určete zbytek po dělení čísla 250 + 350 + 450 číslem 17.
f753
(iii) Určete poslední číslici čísla 79
(iv) Určete poslední číslici čísla 141414.
3 3. týden - RSA šifry, primitivní kořeny
Cvičení konané 18. 3. 2021.
Příklad 3.1: Veřejný klíč Honzy pro RSA šifru je (91, 23). Zachytili jste jemu určenou zprávu 3. Dekódujte ji.
Příklad 3.2:   [10.32, 10.33, slidy] Najděte primitivní kořeny modulo 8, 11, 41 a 412.
4 4. týden — řešení kongruencí
Cvičení konané 25. 3. 2021.
Příklad 4.1:   Vyřešte následující kongruence:
(i) 5x = 12 (mod 23).
(ii) 33a' = 7 (mod 143).
(iii) 210x = 40 (mod 212).
Příklad 4.2:   Vyřešte následující soustavy kongruenci:
(i) 2x = 3 (mod 7), x = 8 (mod 15).
(ii) x = 3 (mod 10), x = 8 (mod 15), x = h (mod 84).
Příklad 4.3:   [10.48, 10.57, 10.58] Vyřešte následující kongruence:
(i) 7x17 = 11 (mod 41).
(ii) x3 = 3 (mod 18),
(iii) x2 = 18 (mod 63).
5   5. týden — kongruence, šifrování
Cvičení konané 31. 3. 2021.
Příklad 5.1:   Vyřešte následující kongruence:
(i) x2 = 1 (moci 30),
(ii) x3 + x + 3 = 0 (mod 25),
(iii) 5x2 + x + 8 = 0 (mod 11),
Příklad 5.2:   Spočtěte následující Legendreův nebo Jacobiho symbol
Příklad 5.3:   [Odjinud, 10.67, 10.68] Rozhodněte, zda následující kongruence mají řešení:
(i) x2 = 5 (mod 227),
(ii) x2 = 5 (mod 229),
(iii) x2 = 38 (mod 65),
(iv) x2 - 23 = 0 (mod 77).
Příklad 5.4:   [10.93] Šifrování:
(i) Ukažte, jak pomocí Rabínova kryptosystému s veřejným klíčem n = 437 zašifrovat a pak dešifrovat zprávu M = 321.
(ii) Martin a Honza chtějí komunikovat šifrou ElGamal. Martin si zvolil prvočíslo 41 s primitivním kořenem 11 a tajný klíč 10, tj. zveřejnil (41,11, A), kde A = ll10 (mod 41). Honza mu poslal veřejným kanálem dvojici (22,6). Jakou zprávu Honza poslal?
(iii) Veřejný klíč Honzy pro RSA šifrování je (33,3). Někdo mu poslal zprávu 7, kterou jste zachytili. Dekódujte ji.
6   6. týden — Booleovské algebry, uspořádané množiny
Cvičení konané 7. 4. 2021.
Příklad 6.1:   Budeme pracovat s výrazy ve výrokové logice.
(i) Zjednodušte výraz (A A B A C) V (A' A B) V (A A B A C).
(ii) [11.116] Nalezněte úplnou disjunktní formu výrazu (B' =>- C) A [(A V C) A 5]'.
Příklad 6.2: [11.124] Určete všechny relací uspořádání na čtyřprvkové množině. Pro každý z neizomorfních typů určete, zda se jedná o svaz. Vyskytuje se mezi uspořádáními Booleova algebra?
Příklad 6.3: [11.126, 11.127] Nakreslete Hasseho diagram svazu dělitelů čísla 36. Je tento svaz distributivní? Jedná se o Booleovu algebru? Pak určete totéž pro dělitele čísla 30.
Příklad 6.4: [11.131] Rozhodněte, zda každý řetězec, který má největší a nejmenší prvek, je úplný svaz.
Příklad 6.5: [11.133] Rozhodněte, zdaje množina konvexních podmnožin v IR3 svazem pro vhodné operace suprema a infima. Pokud ano, je tento svaz úplný či distributivní?
7   7. týden — Polynomy
Cvičení konané 14. 4. 2021.
Příklad 7.1:   [11.76] Rozložte nad IR a C polynom
f{x) = x4 + 2x3 + 3x2 + 2x + l.
Příklad 7.2:   [11.77.] Rozložte polynom f(x) = x5 + 3x3 + 3 nad Q and Z7. Příklad 7.3:   [11.80] Najděte všechny ireducibilní polynomy stupně < 2 nad Z3. Příklad 7.4:   [11.81] Rozhodněte, zda je polynom x4 + x3 + x + 2 ireducibilní nad Z3
8 8. týden — polynomy II.
Cvičení konané 22. 4. 2021.
Příklad 8.1: [11.79]
(i) Eisensteinovo kritérium ireducibility nad Z (tedy i nad Q).
(ii) Určete polynom s racionálními koeficienty co nejmenšího stupně, jehož kořenem je číslo 20V2.
Příklad 8.2:   [11.82, 11.83]
(i) Pro liché prvočíslo p určete všechny kořeny polynomu
f(x) =xp-2 + xp-3 + ... + x + 2.
(ii) Rozložte polynom g(x) = x2 + x + 1 v Z5[:r] and 1*7[x].
Příklad 8.3:   [11.84, 11.84]
(i) Rozložte polynom f(x) = x6 — x4 — 5x2 — 3 v C[x], M[x], Q[x], 1*[x], Z5[x] a 1*7[x] víte-li o něm, že má vícenásobný kořen.
(ii) Rozložte polynom p{x) = x6 + x5 + 4x4 + 2x3 + 5x2 + x + 2 v C[x], M[x], Z2[x], Z5[x] a Z7[x] víte-li o něm, že má vícenásobný kořen i.
(iii) Řešte soustavu p{x) = q(x) = 0 nad C, kde q(x) = x2y2 + y2 + xy + x2y + 2y + 1.
9 9. týden — okruhy
Cvičení konané 28. 4. 2021.
Příklad 9.1: [11.65] Rozhodněte, zda množina R s operacemi © a 0 tvoří okruh, komutativní okruh, obor integrity nebo těleso.
(i)	R =	Z,	a 6	n =	a -	-b	■f 3, a 0 b = —3. [Není okruh.]
(ii)	R =	Z,	a Q	n =	a -	-b	— 3, a Q b = a ■ b — 1. [Není okruh.]
(iii)	R =	Z,	a Q	n =	a -	-b	— l,aQb = a + b — a ■ b. [Je obor integrity.
(iv)	R =	Q,	a d	db =	a -	\-b,	a 0 b = b. [Není okruh.]
(v)	R =	Q,	a d	db =	a -	Vb	+ 1, a 0 b = a + b + ab. [Je těleso.]
(vi)	R =	Q,	a d	db =	a -	Vb	— 1, aQb = a + b + ab. [Není okruh.]
Příklad 9.2: [11.66] Dokažte, že podmožina komplexních čísel Z[i] = {a + 6«|a, 6 G Z} tvoří obor integrity. Jedná se o těleso?
Příklad 9.3:   [11.67] V okruhu matic Mat2,2ÍM) uvažme podokruh matic tvaru
a, b G BL Dokažte, že tento podokruh je izomorfní s tělesem C.
Příklad 9.4:   [11.68] Ukažte, že identita je jediný automorfismu tělesa reálných čísel.
10    10. týden — grupy I.
Cvičení konané 5. 5. 2021.
Příklad 10.1: [11.1] Rozhodněte o následujících množinách a operacích, jakou algebraickou strukturu tvoří (grupoid, monoid, pologrupa, grupa):
(i) podmnožiny množiny přirozených čísel s operací sjednocení [monoid],
(ii) množina N spolu s binární operací nej větší společný dělitel [polorupa],
(iii) množina N spolu s binární operací nej menší společný násobek [monoid],
(iv) množina reálných invertibilních matic 2x2 spolu s operací sčítání matic [není ani grupoid],
(v) množina reálných matic 2x2 spolu s operací násobení matic [monoid],
(vi) množina reálných matic 2x2 spolu s operací odčítán ímatic [grupoid],
(vii) množina invertibilních matic 2x2 nad Z2 spolu s operací násobení matic [grupa],
(viii) množina Z@ spolu s operací násobení (modulo 6) [monoid], (ix) množina Z7 spolu s operací násobení (modulo 7) [grupa].
Příklad 10.2:   11.8 Na množině (IR \ {0}) x IR definujeme operaci 0 jako
(x, y) 0 (u, v) = (xu, xv + y).
Popište, o jakou algebraickou strukturu se jedná.
Příklad 10.3:   [2.19] Rozložte následující permutaci v §9 na součin transpozic:
A  2  3  4  5  6  7 8 9\
\v3 16789542yr
Příklad 10.4:   [11.10] Určete znaménko následujících permutací v §3n a §2n:
'1  2  3  4  5  6  ...  3n - 2  3n - 1 3n
ai     1 2  3  1  5  6  4  ...  3n - 1     3n     3n - 2
_  '1   2  3   ...   n   n + 1   n + 2   ... 2n °"2 ~ 1 2  4  6  ...  2n     1        3     ...  2n - 1
Příklad 10.5:   [11.13] Mějme permutaci a G §7,
'1  2  3  4  5  6 7
a    \3  6  5  7  1  2  4y ' V grupě (§7, o) určete řád a, inverzi k a, a2013 a ukažte, že a nekomutuje s transpozicí r = (2, 3).
Příklad 10.6: [11.16,11.17] Dokažte, že neexistuje čtyřprvková ani pětiprvková nekomutativní grupa.
11    11. týden — grupy II.
Cvičení konané 12. 5. 2021.
Příklad 11.1: [11.19] Určete (až na izomorfismus) všechny komutativní grupy řádu 8. Potom určete, ketrým z těchto grup jsou izomorfní grupy
(ÍÍ) ^1X6,
(iii) Zř7/{±1},
(iv) komplexní kořeny polynomu z8 — 1 = 0 s násobením.
Příklad 11.2: [11.25] Nechť G je grupa dolních trojúhelníkových matic 3 x 3 s jedničkami na diagonále a operací násobení.
(i) Ukažte, že G C G L (3, M.) je podgrupa a rozhodněte, zda je normální.
(ii) Určete centrum Z (G) = {z G G\\/g G G : zg = gz}.
Příklad 11.3:   [11.38, 11.41, 11.42] Podgrupy v symetrických grupách.
12 12. týden — homomosfismy grup, kódy
Cvičení konané 19. 5. 2021.
Příklad 12.1: [11.48] Rozhodněte, zda předpis ip zadává zobrazení, případně zda jde o ho-momorfismus grup (se sčítáním) - pak popište jádro/obraz a rozhodněte, zda je to surjekce či injekce:
(i) <p : Z4 x Z3 -ř Z12, <p([[a]4, [6]3) = [a - 6]12,
(ii) ^ : Z4 x Z3 ^ Zi2, v?([[a]4, [6]3) = [6a + 46]12,
(iii) v? : Z4 x Z3 ^ Z12, v?([[a]4, [6]3) = [0]12.
Příklad 12.2: [11.49] Rozhodněte, zda předpis ip zadává zobrazení, případně zda jde o ho-momorfismus grup (Z& se sčítáním a C* s násobením) - pak popište jádro/obraz a rozhodněte, zda je to surjekce či injekce:
(i) v?:Z4^C\ v?(M4) = ia,
(ii) v?:Z5^C*, v9([[a]5)=ía,
(iii) v? : Z4 ^ C*, v?(M4) = (-^)a,
(iv) v? : Z -> C*, v?(a) = ia
Příklad 12.3: [11.136] Uvažme (5, 3)-kód nad Z2 generovaný polynomem x2 + x+ 1. Vypište všechna kódová slova, najděte generující matici a matici kontroly parity.
13 13. týden — kódování
Cvičení konané 26. 5. 2021.
Příklad 13.1: [11.138] Sedmibitové zprávu a0 ... a6 chápanou jako a0 + aľx + ... + a6x6 kódujeme polynomiálním kódem generivaným polynomem p(x) = x4 + x + 1.
(i) Zakódujte zprávu 1100011.
(ii) Obdrželi jste kód 10111010001. Jaká byla posílaná zpráva za předpokladu, že k chybě došlo maximálně v jednom bitu?
(iii) Jaká byla zpráva v (ii) za předpokladu, že k chybě došlo právě na dvou bitech?
Příklad 13.2: [11.141] Určete generující matici a matici kontroly parity (7, 2)-kódu generovaného polynomem x5 + x4 + x2 + 1. Dekódujte přijaté slovo 0010111 (tj. určete poslanou dvoubitovou zprávu) za předpokladu, že při přenosu došlo k nejmenšímu možnému počtu chyb.
Příklad 13.3: V lineárním (7,4)-kódu (tj. dálka zprávy před zakódováním je 4) nad Z2 zadaném maticí
/o	1	1	o\
1	1	0	1
1	0	1	1
1	0	0	0
0	1	0	0
0	0	1	0
V>	0	0	v
byla přijata zpráva 1010001. Dekódujte ji za předpokladu, že při přenosu došlo k nejmenšímu možnému počtu chyb.