1. domácí úloha z MIN401, jaro 2024
Příklad 1. Martin řešil rovnici x ■ 5X = 3 (mod 17).
(1) Najděte jedno řešení této rovnice. Martin jej hledal následovně. Protože je zjevně 3 = 3-1, zkusil hledat x splňující
x = 3   (mod 17)
5X = 1   (mod 17).
U druhé kongruence se vám může hodit, že 5 je primitivní kořen modulo 17.
(2) Toto řešení x není zbytková třída modulo 17 (to třeba znamená, že když x je řešení, tak x + 17 řešením být nemusí), ale modulo vhodné m. Najděte takové m.
(3) Určete počet řešení původní kogruence (modulo m), tato další řešení hledat nemusíte! Doporučený postup: Určete počet způsobů, jak rozložit 3 = a ■ b (mod 17) (kolik existuje pro dané a příslušných 6?) a určete, pro která z těchto a, b má soustava
x = a   (mod 17) 5X = b   (mod 17)
řešení a kolik jich je modulo m. Využijte, že 5 je primitivní kořen modulo 17.
Příklad 2. Zbytek x se nazývá idempotent modulo n, jestliže x2 = x (mod n). Příkladem idempotentů jsou 0 a 1. Z přednášky víme, že pro prvočíselný modul už žádné další neexistují (kvadratická rovnice má maximálně dvě řešení).
a) Najděte zbylé dva idempotenty y a z modulo m = 11-19, přičemž je asi dosti výhodné „řešit" rovnici prvně zvlášť modulo 11a modulo 19 a pak dát tyto výsledky dohromady.
b) Studujte celočíselné lineární kombinace x = k-y + l-z idempotentů y a z z předchozího bodu a zejména jejich zbytky modulo 11 a 19 a ukažte, jak lze takto pomocí y a z snadno napsat řešení soustavy kongruencí
x = a   (mod 11)
x = b   (mod 19)
l