1. vnitrosemestrální práce MB104, 17. 3. 2014 skupina A
Příklad 1. (3b.) Určete poslední dvě cifry čísla 2
Řešení. Určíme hledaný zbytek po dělení číslem 100: ten je jednoznačně určen zbtky po dělení čísly 25 a 4. Zřejmě je zbytek po dělení čtyřmi nulový (45 > 2), navíc protože (2, 25) — 1 je 2<p(25) — 220 = 1 (mod 25). Dále je 45   dělitelné čtyřmi a dává zbytek —1 po dělení pěti (je to —1 na lichou), tedy zbytek 4 po dělení
dvaceti. Je tak 24°    = 220fe+4 = 220fe24 = 24 = 16   (mod 25). Protože 4|16 je tento zbytek zbytkem i po dělení stem. Poslední dvě cifry daného čísla tedy jsou 1 a 6. Příklad 2. (5b.) Vyřešte soustavu kongruencí
20x   = 150      (mod 250) llx    = 17       (mod 21)
Řešení. Vyřešíme nejprve první kongruenci (můžeme zkrátit levou, pravou stranu a modul kongruence společným dělitelem 10. Řešíme tedy kongruenci 2x = 15 (mod 25). Pomocí Eukleidova algoritmu nalezneme inverzi ke dvojce: 13, pronásobením číslem 15 dostáváme řešení 20), lze i „uvidět" přímo, (také je možné si všimnout, že x musí být násobkem pěti (x — 5í) a řešíme jednodušší kongruenci 2í = 3 (mod 5)). Dosazením x — 25í + 20 do druhé kongruence pak dostáváme po odečtení násobků sedmi kongruenci 2t = 7 (mod 21), s řešením t — 21u + 14. Celkem x — 525w + 370.
Příklad 3. (2b.) Nalezněte všechna kladná celá k a n, pro která je číslo 2kn+2 + kn prvočíslo.
Řešení. Číslo zapíšeme ve tvaru součinu: 2kn+2 + kn — kn(2k2 + 1). Pro k > 2 jsou oba činitelé větší než 2 a nemůže se tedy jednat o prvočíslo. Pro k — 1 vyhovuje libovolné celé kladné n.
1