První zkoušková práce, 20. 5. 2014 skupina B
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 + 4 a 8n + 1 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 + 4) — 5 • (8n+ 1) — 27. Musí tedy být roven některému z (kladných) dělilů čísla 27, neboli některému z čísel 1, 3, 9, 27. Všechny varianty jsou vskutku možné (posupně pro n — 0, n — A, n — í a n — 10).
Příklad 2. (5b.) Určete nějaký primitivní kořen modulo 79. (79 je prvočíslo. Vzpomeňte na druhou vnitro-semestrálku. Můžeme říci něco o 39-té mocnině hledaného primitivního kořene?)
Řešení. Víme, že 39-tá mocnina primitivního kořene modulo 79 musí být kongruentní s —1 modulo 79. Postupujeme od nejmenšího čísla (pro jednoduchost). Spočítáme 239 = 1 (mod 79), 339 = —1 (mod 79), je tedy 3 možný primitivní kořen. Je nutno ověřit, jestli 378/9 ^ 1 (mod 79) pro libovolné prvočíslo q dělící if (79) — 78, v našem případě zbývá ověřit 6-tou a 26-tou mocninu. Spočítáme 36 = 18 (mod 79) a 326 = 23 (mod 79), je tedy číslo 3 vskutku primitivním kořenem.
Příklad 3. (4b.) Metodou vytvořujících funkcí nalezněte posloupnost (xn) splňující pro n > 1:
2^n+2 — xn+l + xni     xl — 1;  x2 — 3.
Řešení. Podle podmínek zadání musí vytvořující funkce A{x) posloupnosti [x\, X2, x3, ■ ■ ■ ] splňovat rovnici:
2A(x) = xA(x) + x2A(x) + 2 + 5x,
tedy
2 + 5x    _ 7   1       8 1 ^ ~ 2-x-x2 ~ 3 ~ 3lTf'
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
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ý?
1