1. TŘETÍ PÍSEMNÁ ZKOUŠKA MB204 18.6.2013
1.1. Mějme kongruenci 922 • x = 1284 (mod 644). Pomocí kritéria udávajícího řešitelnost (a počet řešení) lineární kongruence určete počet řešení této kongruence a pak kongruenci vyřešte.
Řešení. 922 = 2.461, 1284 = 22.3.107 a 644 = 22.7.23. Platí (922,644) = 2|1284, soustava má tedy právě dvě řešení modulo 644. Podle čínské zbytkové věty je kongruence ekvivalentní soustavě
x = 0   mod 2 6x = 5   mod 7 x = 21   mod 23
Řešením je x = 44 nebo x = 366 mod 644. □
1.2. Určete cr"1 a cr2013, kde
, ,        A   2345678   9\ , , , 9 ,
• (a)cr=l3   4   5   2   7   g   9   g   J v grupe permutaci (Sy,o).
• (b) cr= [4]i3 v grupě (Z* ,-)■
Řešení, (a) cr = (1,3,5,7,9) o (2,4) o (6,8), cr"1 = (1,9,7,5,3) o (2,4) o (6,
(7
2013 _ ^3 = (1; 7j 3j 9j 5) Q (2; 4) o (6; 8). (b) 46 = 1 mod 13 ^ a-i
45 = -3 = 10 mod 13 a cr2013 = 42013 = 43 = -1 = 12 mod 13. □
1.3. Je dána soustava polynomiálních rovnic
x2yz2 + x2y2 + yz — xyz2 — z2 — 0 x2y + z — 0 xyz + z + í — 0
Seřaďte monomy polynomů podle lexikografického uspořádání s x > y > z, pak vydělte první polynom druhým a třetím a výsledek využijte k vyřešení soustavy v oboru reálných čísel.
Řešení. x2y2 + x2yz2 — xyz2 +yz — z2 — (y + z2)(x2y + z) — y(xyz + z + 1) — z3 + z. Odtud z — 0, ±1. Potom např. 0 — z(x2y + z) —x(xyz + z +1) — z2 — zx — x. Odtud
x — -^j-j- a z třetí rovnice y — —        ■ Vyhovuje jediný reálný bod (^, —4,1). □
1.4. Sedmibitovou zprávu a$ai... ae, chápanou jako ao+a±x+- ■ -+a,QXe, kódujeme polynomiálním kódem generovaným polynomem x4 + x3 + 1.
• (a) Zakódujte zprávu 1100110.
• (b) Obdrželi jste kód 00111010111. 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 = x3 + 1, x5 = x3 + x + 1, x6 = x3 + x2 + x + 1, x7 = x2 + x + 1,
řjj8 - jr^*     j     jr^,     j     rjt   jry^ - jr^,     j     ^      UJ^"^ - j     £ -\>    ^     j     jr»     j     rj>^     j     jr^i   |_y   jr»^     j     jr^i     j j
x9 + x3 + l+x3+x + l + x3 + x2+x + x2 + l = l+x3+x4 + x5 + xs + x9. Kód je tedy 10011100110. (b) x2 + x3 + x4 + x6 + xs + x9 + x10 dává po dělení x4 + x3 + 1 zbytek x5. Došlo tedy k chybě na šestém bitu a původní zpráva byla 1110111. (c) x5 = x3 + x + 1 = 1 + x10 = x + x4 = x2 + x6 = xs + x9. Buď tedy nastala chyba na prvním a posledním bitu nebo na druhém a pátém nebo třetím a sedmém nebo na devátém a desátém. V prvním případě byla zpráva 1010110, ve druhém 0010111, ve třetím 1000111 a ve čtvrtém 1010001. □
1