1. domácí úloha z MIN401, jaro 2024
Příklad 1. Martin řešil rovnici x ■ 5X = 3 (mod 17).
a) 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.
b) 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.
c) 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.
Řešení.
a) Druhá rovnice je ekvivalentní x = 0 (mod 16), díky tomu, že 5 je podle zadání primitivní kořen. Řešíme tedy soustavu
x = 3   (mod 17)
x = 0   (mod 16)
kde dosazením x = 17t + 3 do druhé kongruence dostáváme t = 13 (mod 16), celkově pak x = 224 (mod 272).
b) Výše jsme odvodili m = 272.
c) Při rozkladu 3 = a ■ b (mod 17) bude, podobně jako v prvním bodě, soustava ze zadání ekvivalentní
x = a   (mod 17)
x = log17 b   (mod 16)
a podle čínské zbytkové věty bude mít jediné řešení modulo m = 272. Přitom pro každé nenulové a (mod 17) existuje jediné 6 = 3- cT1 (mod 17). Protože je rozkladů 16, a pro každý existuje jedno řešení, máme dohromady 16 řešení.
□
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.
i
2
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)
Řešení.
a) Protože modulo 11 i modulo 19 máme pouze dvě řešení 0 a 1, a tyto můžeme libovolně kombinovat, budou zbylí dva idempotenti řešeními soustav
Jejich vyřešením standardním způsobem dostaneme y = 133 (mod 209) a z = 77 (mod 209).
b) Z kongruencí pro y a z z prvního bodu dostáváme pro x = k ■ y + / • z úpravou
x = k-l + l-0 = k (modli)
x = k ■ 0 + / • 1 = /   (mod 19)
Dostáváme tak k = a (mod 11) a / = b (mod 19) a řešením obecné soustavy kongruencí je tedy x = a ■ 133 + 6-77 (mod 209).
y = 1 (mod 11) y = 0   (mod 19)
2 = 0 (mod 11) z = 1   (mod 19)
□