M6520 Jméno:
5.1.2018
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 90 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 Pro libovolná x, y G N existují k, l G N tak, že k ■ x + / • y = (x, y).
(b) ano — ne Je-li m G N, pak pro každé přirozené číslo d takové, že d \ ip(m) existuje x G Z řádu d modulo m.
(c) ano — ne Pro všechna přirozená čísla n > 1 platí Y2d\n L1 (d) = 0 (/^ z<^e označuje Môbiovu funkci).
(d) ano — ne Je-li 2n — 1 prvočíslo, pak je i n prvočíslo.
(e) ano — ne  Libovolná redukovaná soustava zbytků modulo prvočíslo p > 2 obsahuje stejný počet kvadratických zbytků a nezbytků.
(f) ano — ne Rovnost v Cauchyově nerovnosti (xf + x^ + x^^yf + y^ + y2) > (x1y1+x2y2 + %3y3)2 nastává právě když x\ = y±,X2 = y2,%3 = ž/3-
2. (6 bodů) Nechť p je prvočíslo. Dokažte (aniž byste se pouze odkázali na příslušnou větu) :
i) (p — 1)! = — 1 (mod p).
ii) Pro celé číslo 0 < a < p — 1 platí
(^~1'Sj=(-1)a (modp). (Poznámka: Obě částí lze řešit nezávisle na sobě.)
3. (6 bodů) Jedenáct děvčat a n chlapců se vydalo na houby. Celkem nasbírali n2 + 9n — 2 hub, přitom každý z houbařů (i houbařek) našel stejný počet hub. Určete počet hub, který každý nasbíral.
4. (8 bodů) Určete nějaký primitivní kořen modulo 113. Dále určete všechna celá čísla 0 < a < 113, pro něž platí
7092 + 1 = a26   (mod 113).
5. (6 bodů) Řešte v oboru celých čísel rovnici
2x2 + xy = y2 + 63.
6. (4 body) Alice chce zašifrovat zprávu pomocí RSA, vybere si n = 17 ■ 19 = 323 a e = 65 jako svůj veřejný klíč. Proveďte výpočet Alicina soukromého klíče. Dále s využitím algoritmu modulárního umocňování vypočtěte, jak Bob zašifruje pro Alici zprávu "B" (zakódovanou do čísla 2). Uveďte též (již bez výpočtu), jak Alice tuto zprávu dešifruje.