Vnitrosemestrální práce MB204 1.4.2014 A
1 (2,5b). Dokažte, že pro libovolné n e N je číslo 23  + + 3 složené.
Řešení. Dokážeme 11|23 + +3. Z Eulerovy (Fermatovy) věty je 210 = 1 (mod 11) a protože ip(10) = 4 a (3,10) = 1, platí také 34 = 1 (mod 10). Odtud 34n+1 = 3 (mod 10) a 234"+1 = 23 = 8 (mod 11). Celkem 234"+1 +3 = 0 (mod 11).
2 (2,5b). Mějme kongruenci 1480x = 9135 (mod 455). 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í. Zjistíme (1480,455) — 5|9135, a proto má kongruence pět řešení mo-dulo 455. Ty jsou dané podmínkou 296x = 1827 (mod 91). Protože 91 — 7 ■ 13, dostáváme ekvivalentní soustavu 8x = 0 (mod 7), lOx = 7 (mod 13). Odtud x — 7t a t = 4 (mod 13), tj. x = 7 ■ 4 — 28 (mod 91). Pět řešení modulo 455 pak má tvar x = 28,119, 210,301,392.
3 (2,5b). Dokažte neexistenci primitivních kořenů modulo 28.
Řešení. Protože if (28) — tp(4)(p(7) — 12, stačí testovat g4 a g6. Primitivní kořen musí být zejména nesoudělný s modulem. Také nemusíme testovat mocniny menších čísel (jejich řád dělí řád základu). A protože 15 = —14, • • • ,25 = —3 a počítáme jen sudé mocniny, stačí otestovat následující
9	3    5   11 13
92	9-391
94	-3   9-3 1
9"	1111
Řád všech nesoudělných čísel s 28 je tedy maximáklně 6, nikoli 12.
4 (2,5b). Mějme kongruenci 5x31 = 9 (mod 26). Pomocí kritéria udávajícího řešitelnost (a počet řešení) binomické kongruence určete počet řešení této kongruence a pak kongruenci vyřešte. Kolik existuje primitivních kořenů modulo 26? Řešení. Je výhodné si kongruenci hned na začátku rozdělit na soustavu x31 = 1 (mod 2), 5x31 = 9 (mod 13). První kongruence nám říká, že x je liché, zatímco druhá je ekvivalentní x31 = 7 (mod 13). Protože ip(13) = 12, (12, 31) = 1 a 712 = (—3)6 = (—4)3 = 1 (mod 13), má daná kongruence právě jedno řešení modulo 26. Primitivní kořen pro 13 je g — 2 a 7 = 211, a proto dostáváme 31xa = 11 (mod 12). Této kongruenci vyhovuje právě xa = 5 (mod 12). Odtud x = 25 = 6 (mod 13). Navíc musí být liché, tj. x = 19 (mod 26). Libovolný primitivní kořen g generuje celou redukovanou zbytkovou třídu. Proto každý jiný primitivní kořen můžeme napsat jako gk pro vhodné k. Řád g je if (26) — 12, a proto je řád gk roven 12 (maximální) právě tehdy, když (k,(p(26)) — 1. Takových k < 12 je tedy právě (p((p(26)) — (p(12) = 4a stejný počet je primitivních kořenů.
i