Vnitrosemestrální písemka - MIN401 - jaro 2021 - 30. 4. 2021
Veškeré odpovědi musí být zdůvodněny a výpočty musí být doprovozeny komentářem. (Řešení sestávající pouze z odpovědí budou považována za opsaná a hodnocena 0 body.)
1. (3 body)
(i) Ukažte, že 5|(6741 + 2)9 + 1.
(ii) Rozhodněte, zda 25|(6741 + 2)9 + 1.
2. (5 bodů)
(i) Rozhodněte, zda existuje primitivní kořen modulo 32.
(ii) Určete inverzní prvek k 5 modulo 32.
(iii) Určete řád 5 modulo 32.
(iv) Najděte nějaké a E Z řádu 2 modulo 32.
(v) Určete počet prvků v množinách
M1 = {1,5,52,53,...}      a      M2 = {-1,-5,-52,-53,...}
modulo 32 a rozhodněte, které z těchto prvků jsou invertibilní.
(vi) Ukažte, M1 n M2 = 0 modulo 32.
(vii) Ukažte, že každé x splňující kongruenci
x3 = 25   mod 32 je invertibilní modulo 32 a pak tuto kongruenci vyřešte.
3. (2 body) Nalezněte všechna řešení kongruence
3a-2 - 4x + 17 = 0   mod 13.
Řešení a bodování:
[3 body]
(i) Modulo 5 platí
(6741 + 2)9 + 1 = (241 + 2)9 + 1 = (21(M+1 + 2)9 + 1 = (2 + 2)9 + 1 = (-1)9 + 1 = 0,
neboť 2^5) = 24 = 1 mod 5.
(ii) Modulo 25 platí
(6741 + 2)9 + 1 = (1741 + 2)9 + 1 = (172'20+1 + 2)9 + 1 = (17 + 2)9 + 1 = 199 + 1 = (-6)9 + 1, neboť 17<ŕ(25) = 1720 = 1 mod 25. Dalším výpočtem modulo 25 dostaneme
(-6)9 + 1 = -29 • (33)3 + 1 = -29 • 23 + 1 = -642 + 1 = -142 + 1 = -196 + 1 = -(-4) + 1 = 5, tj. 25 nedělí (6741 + 2)9 + 1. [5 bodů]
(i) Neexistuje, neboť 32 není mocnina lichého prvočíslo ani dvojnásobek mocniny lichého prvočísla.
(ii) Inverzní prvek k 5 modulo 32 jistě existuje, protože (5, 32) = 1. Z Bezoutovi rovnosti 5 • 13 — 2 • 32 = 1 plyne 5-13=1 mod 32, tedy hledaná inverze je 13.
(iii) Máme if (32) = 16, což má dělitele tvaru 2k, 0 < k < 4. Tedy možné řády jsou 2, 4 a 8 (16 by byl řád primitivního kořene, který 32 nemá). Postupným zkoušením se zjistí, že řád 5 je 8.
(iv) 54.
(v) Platí \Mi\ = IM2I = 8, protože řád 5 modulo 32 je 8. Prvky v těchto množinách jsou liché a tedy invertibilní.
(vi) Je-li a e Mi n M2, 0 < i, j < 7 pak a = 5* = —5J mod 32. Předpokládejme i < j (opačná nerovnost se ukáže podobně); pak 5* +5J = ^fó^1 + 1) = 0 mod 32, tj. 5J_Í = —1 mod 32. Vzhledem k řádu 5 pak nutně j — í = 4, ale přímým výpočtem se lehce ověří, že 54 ^ — 1 mod 32.
(vii) Invertibilní jsou čísla nesoudělná s 32, což jsou právě lichá čísla. Tedy každé řešení x kongruence je invertibilní, tj. x = 5^ nebo x = —5^ pro nějaké 0 < £ < 7. v Prvním případě dosazením dostaneme 53^ = 52 mod 32, tj. 31 = 2 mod <p(32), tj. 53^ = 52 mod 16. Tato kongruence má jediné řešení £ = 6 mod 16, tj. řešením kongruence je 56 mod 32. Případ x = —5^ nemůže být řešením, neboť Mi n M2 = 0.
[2 body] Levou stranu kongruence vynásobíme 4 (abychom u x2 dostali koeficient —1) a upravíme modulo 13:
4(3x2 - Ax + 17) = -x2 - 3x + 3 = x2 + 3x - 3 = x2 - lOx - 3 = (x - 5)2 - 28 = (x - 5)2 - 2.
Substitucí y = x — 2 dostaneme kongruenci y2 =2 mod 13, která nemá řešení. Vskutku, použitím kritéria z přednáška pro d := (3, ^(13)) = 3 dostaneme 2^~ = 2^ = 24 ^ 1 mod 13. Zadaná kongruence 3x2 — Ax + 17 = 0 mod 13 tedy nemá řešení.