První písemná zkouška MB204 22.5.2013
1. Ukažte, že nejmenší primitivní kořen modulo 41, tj. generátor grupy (Z^, •), je g — 6. Tohoto kořene využijte k vyřešení binomické kongruence x2 = 4 (mod 41). Můžeme říct, kolik řešení má tato kongruence modulo 41, aniž bychom je museli explicitně spočítat?
~ 41 — 1 41 — 1 41 — 1 41 — 1
Řešení. 2^~~ = 1, 3^^~ = 1, 5^~~ = 1 mod 41 a zároveň 6^~~ e 10 ^ 1 a 6^ = -1 mod 41. Dále 66 = -2 ^> 4 = 612 a tedy pro x = 6* platí 62t = 612 mod 41, což je ekvivalentní 2t = 12 mod (^(41) = 40, tj. í = 6 mod 20. Řešením je tedy 66 = —2 a 626 = 2. Kopngruence má právě dvě řešení protože (^(41) = 40 a (40, 2) = 2 a 4~ = 420 — 22 20 = 1. Tím pádem hned víme, že kongruence má právě řešení x = ±2. □
2. O polynomu p — xe + x5 + 4x4 + 2x3 + 5x2 + x + 2 víte, že má vícenásobný kořen x — i. Rozložte jej na ireducibilní polynomy v C[x], M.[x], Z2[x], Z5[x] a 7h-{\x\. Polynom q — x2y2 + y2 +xy + x2y + 2y +1 vydělte se zbytkem ireducibilními faktory polynomu p v M.[x] a výsledek využijte k vyřešení soustavy polynomiálních rovnic p — q — 0 nad C.
Řešení, p = (x2 + l)2(x2 + i+2),vZ2:p = x (x + l)5, v Z5: p = (x - 2)2(x + 2)2(x2 + x + 2), v Z7: p — (x2 + l)2(x + 4)2. Pro druhý polynom dostáváme q — (y2 + y)(x2 + x + 2) - y2(x + 1) + 1 ag = (y2 + y)(x2 + 1) + y(x + 1) + 1. Je-li tedy x — a kořenem x2 + x + 2, tj. a = —^ ± ^í\/7, pak je y = -Pokud x = (3 je
kořenem faktoru x2 + 1, tj. f3 — ází, pak je y — —j^p d
3. Sedmibitovou zprávu a$ai... ci,q, chápanou jako ao+aix+- ■ -+a,qxe, kódujeme polynomiálním kódem generovaným polynomem x4 + x + 1.
• (a) Zakódujte zprávu 1100011.
• (b) Obdrželi jste kód 10111010001. Jaká byla posílaná zpráva, když budete předpokládat, že došlo k chybě na maximálně jednom bitu?
• (c) Jaká byla zpráva v (b), pokud předpokládáme, že došlo k chybě právě na dvou bitech?
Řešení, (a) x4 = x+í, x5 = x2+x, x9 = x3+x, xw = x2+x+í =>• í+x+x5+x6 i->-x4 + x5 + x9 + x10 + x + 1 + x2 + x + x3 + x + x2 + x + 1 = x3 + x4 + x5 + x9 + x10. Kód je tedy 00011100011. (b) 1 + x2 + x3 + x4 + x6 + xw dává po dělení x4 + x + 1 zbytek x2 + 1 = xs. Došlo tedy k chybě na devátém bitu a původní zpráva byla 1010101. (c) Buď nastala chyba na prvním a třetím bitu (x2 + 1), nebo na pátém a šestém (x4 + x5 = x2 + 1). V prvním případě byla zpráva 1010001, ve druhém 0110001. □
4. Najděte vytvořující funkci a explicitní vyjádření pro n-tý člen posloupnosti {an} definované rekurentním vztahem
a,o — 1, «i — 2
an — 4a„_i — 3a„_2 + 1 pro n > 2.
Řešení. Univerzální formule platná pro všechna n G Z je an — 4a„_i — 3a„_2 +
1 — 3[n — 1]. Vynásobením xn a sečtením přes všechna n dostaneme rovnici pro
00 2 vytvořující funkci A(x) —       v", ze které vyjádříme A(x) — (?*xy^^x\ —
n—0
- iitíf + ™- takže člen u xn Je a* = K-1)^ n1) - é(-i)n("„2) + !(-3)n t™1) = ! - > +1) +13" = □
1