První zkoušková práce, 20. 5. 2014 skupina A
Příklad 1. (5b.) Najděte všechna celá kladná čísla, která mohou být největším společným dělitelem celých čísel 5n + 6 a 8n + 7 pro nějaké n e Z. (Uvažte, že NSD(a, b) — NSD(a, a — b)).
Řešení. Víme, že největší společný dělitel daných čísel musí dělit libovolnou jejich lineární kombinaci, tedy i 8 • (5n + 6) — 5 • (8n + 7) — 13. Je tedy buď roven číslu 1, nebo číslu 13. Obě varianty jsou možné (pro n — 1 je NSD jedna a pro n — 4 je NSD roven číslu 13).
Příklad 2. (5b.) Určete nějaký primitivní kořen modulo 97.
Řešení. Víme, že 48-má mocnina primitivního kořene modulo 97 musí být kongruentní s —1 modulo 97. Postupujeme od nejmenšího čísla (pro jednoduchost). Spočítáme 248 = 1 (mod 97), 348 = 1 (mod 97), čtyřka primitivním kořenem být nemůže nikdy (4R2~ — 2P~1 = 1 (mod p), modulo libovolné liché číslo), dále dostáváme 548 = —1 (mod p). Je tedy 5 možný primitivní kořen. Je nutno ověřit, jestli 596/9 ^ 1 (mod 97) pro libovolné prvočíslo q dělící (p(97) — 96, v našem případě zbývá ověřit už jen 32-hou mocninu. Spočítáme 532 = 35 (mod 97), je tedy číslo 5 vskutku primitivním kořenem.
Příklad 3. (4b.) Metodou vytvořujících funkcí nalezněte posloupnost (xn) splňující:
xn+2 — xn+l + 2aľ„,     Xi —3,  X2 — 1.
Řešení. Podle podmínek zadání musí vytvořující funkce A(x) posloupnosti [x\,X2,x%,.. . \ splňovat rovnici:
A(x) = xA(x) + 2x2A(x) + 3 - 2x,
tedy
3-2x     _ 5   1       4 1 ^ ~ 1 - x - 2x2 ~ 31+x + 3 1 - 2x'
U této funkce už umíme (např. podle zobecněné binomické věty) určit jednotlivé koeficienty v jejím rozvoji do mocninné řady. Přímo tak odečteme, že n-tý koeficient, tedy (n+ 1) člen hledané posloupnosti (nesmíme zapomenout na úvodní posun) je
on+l r
Příklad 4. (6b.) Kolika způsoby lze vybrat 60 kuliček tří barev (červená, modrá, zelená), přičemž počet červených a modrých je sudý?
Řešení. Všimněme si, že ze zadání vyplývá, že počet kuliček libobolné barvy musí být sudý. Úloha se tedy transformuje (vydělením počtů kuliček dvěma) na úlohu vybrání 30 kuliček tří barev bez omezení na počty kuliček jednotlivých barev. Tu již standardně vyřešíme: hledaný počet je roven koeficientu u x30 ve výrazu
(l+x + x2-\----)3 1
(1 -x)3
a ten podle zobecněné binomické věty je roven (322).
1