MUC33 Jméno: .
6.1.2025
Na každý příklad získáte nezáporný počet bodů. Minimum (včetně semestrální písemky) je 30 bodů. Na práci máte 100 minut.
Hodnocení				Sem.	
					
					
1. (6krát ±1 bod — správně 1 bod, chybně —1, bez odpovědi 0) Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující tvrzení (čtěte velmi pozorně!):
(a) ano — ne Existuje 2 7 primitivních kořenů modulo prvočíslo p = 28 + 1.
(b) ano — ne Pro libovolné m G N \ {1} existuje nekonečně mnoho prvočísel dávajících zbytek 1 modulo m.
(c) ano — ne Je-li n prvočíslo, pak je i 2n — 1 prvočíslo.
(d) ano — ne Pro všechna přirozená čísla n > 1 platí X^nM^) = 0 (/^ z(^e označuje Môbiovu funkci).
(e) ano — ne Libovolná polynomiální kongruence f(x) = 0 (mod m), kde m G N a ne všechny koeficienty polynomu / jsou násobky m, má nejvýše st(/) řešení modulo m.
(f) ano — ne Relace dělitelnosti je na množině přirozených čísel relací uspořádání.
2. (6 bodů) Přirozené číslo x a prvočíslo p mají tu vlastnost, že obsah obdélníku o stranách x a 2x — 1 je o 36 větší než obsah čtverce o straně p. Určete všechny možné hodnoty x a, p.
3. (8 bodů) Řešte kongruenci 3Cte2 + 7x + 180 = 0 (mod 473). (Nápověda: Modul není prvočíslo.)
4. (6 bodů) Rozhodněte, pro která přirozená čísla n je číslo 5n + 4n + 1 dělitelné třinácti.
5. (6 bodů) Na školní zahradě hraje skupina žáků hru zvanou molekuly. Učitel jim nejprve uložil, aby se rozdělili do trojic. Jeden žák přebyl, a tak z další hry vypadl. Zbylí žáci se pak měli rozdělit do čtveřic. Opět jeden žák přebyl a vypadl. Poté se zbylí žáci měli rozdělit do pětic, zase jeden žák přebyl a vypadl. Učitel nyní ukládá, aby se zbylí žáci rozdělili do šestic.
(a) Dokažte, že opět jeden žák přebyde.
(b) Kolik nejméně žáků mohlo být původně na dvoře?
6. (8 bodů)
(a) Určete nějaký primitivní kořen g modulo 71. S jeho pomocí určete všechna x (0 < x < 71), pro něž
71 | x22 + 7.
(6 b.)
(b) Alice a Bob si chtějí vyměnit tajný klíč (číslo) protokolem Diffieho a Hellmana s parametry p = 71 a g z předchozí části. Ukažte (výpočtem pro oba zúčastněné), na jakém čísle se shodnou, pokud Alice použije (jako svůj tajný exponent) číslo 6 a Bob číslo 9. Popište též, jak probíhá jejich komunikace. (2 b.)