Cvičení MB204 Teorie čísel Úvod Podmínky zápočtu atd. 1. Dělitelnost 1.1. Nalezněte všechna celá čísla a^3, pro která platí a — 3|a3 — 3. Řešení, a - 3|a3 - 27 a proto a - 3|a3 - 3^a- 3|a3 - 3 - a3 + 27 = 24. □ 1.2. Pro která celá čísla n je In + 1 dělitelné 3n + 4? Řešení. 3n + 4|7n+l => 3n + 4|7(3n + 4) - 3(7n+1) = 25. Odtud n e {-3,-1,7} □ 1.3. Dokažte, že pro všechna celá čísla a, b platí 17|2a + 36 <ŕ=> 17|9a + 56. Řešení. 2a + 36 — 4(9a + 56) — 17(2a + 6). Koeficienty lze odvodit z Bezoutových koeficientů (Euclid). □ 1.4. Dokažte, že pro všechna přirozená čísla n platí 9|4™ + 15n — 1 Řešení. Indukcí nebo Binomickou větou. □ 2. Dělení se zbytkem, GCD, LCM, Euklidův algoritmus, Bezoutova věta 2.1. Dokažte, že mezi to po sobě jdoucími čísly existuje právě jedno dělitelné to. Řešení. Označme čísla a + 1,..., a + to. Podle věty o dělení se zbytkem 3\q, r < m : a — q.m + r. Pak a + (to — r) — m(q + 1) je hledané číslo. Ostatní nenulový zbytek. □ 2.2. Určete největší společný dělitel (21, 98) a najděte koeficienty v Bezoutově rovnosti. Řešení. (21,98) = 7 = 5.21 -98. □ 2.3. Určete největší společný dělitel (10175, 2277) a najděte koeficienty v Bezoutově rovnosti. Řešení. (10175, 2277) = 11 = (-32).10175 + 143.2277. □ 2.4. Určete největší společný dělitel (2n + 1, 9n + 4) a (2n — 1, 9n + 4). Řešení. (2n+l, 9n+4) = (2n+í,n) = (n, 1) = 1 a (2n-l, 9n+4) = (2n+l, n+8) = (-17, n + 8). Odtud 17|n + 8 ^> GCD = 17 a 17 \ n + 8 ^> GCD = 1. □ 2.5. Určete největší společný dělitel čísel 263 — 1 a 291 — 1. Řešení. 291 - 1 = 228(263 - 1) + 228 - 1 a 263 - 1 = (235 + 27)(228 - 1) + 27 - 1. Protože 27- 1|228 - 1, je GCD=27 - 1. □ 2.6. Spočítejte největší společný dělitel tří čísel (252, 364,455). Řešení. 455 = 364 + 91,364 = 4.91 a 252 = 2.91 + 70,91 = 70 + 21,70 = 3.21 + 7,21 = 3.7. Odtud (252, 364,455) = 7. □ 2.7. Dokažte (a, 6).(c, (i) = (ac, ad, bc, bd). Řešení. Označme dělitele d\, d,2, «V Bezout: 3k, l : ak+bl — d\ a 3to, n : cm+dn — d,2- Odtud d\d,2 — km.ac+kn.ad+lm.bc+ln.bd a podle Bezouta pro P pak d^\did2-Naopak zřejmě d±\a,d2\c, tj. d\d2\ac atd. Dohromady dio^oV Nebo: (ac, ad, 6c, 6d) = (a(c, d), 6(c, d)) = (a, 6).(c, d). □ 2 2.8. Dokažte abc — [a, b, c].(ab, ac, bc) Řešení, d := (ab,ac,bc). Pak f € N a a,b,c\^. Odtud ^ = q.[a,b,c}. Dále 9lf.f.Taprotog|(^,f,^) = l. □ 3. Prvočísla 3.1. Mezi kterými deseti po sobě jdoucími čísly je nejvíce prvočísel? Řešení. 1,2,.. ~> 4, 2,3,.. ~> 5, 3,4,.. ~> 4, 4,5,.. ~> 4. Pět sudých, jedno ze tří po sobě jdoucích lichých je vždy dělitelné třemi. □ 3.2. Nalezněte všechna prvočísla, která jsou zároveň součtem i rozdílem nějakých dvou prvočísel. Řešení. Parita dá, že jedno musí být rovno 2. Je tedy p — 2, p, p + 2 prvočísla. Jedno z nich dělitelné třemi. Odtud p — 5 □ 3.3. Dokažte, že pro žádné n není možné 6n + 5 vyjádřit jako součet dvou prvočísel. Řešení. Parita dá, že jedno musí být rovno 2. Je tedy 6n + 5 — p + 2, tj. p — 3(2n+l). □ 3.4. Nalezněte všechna prvočísla p, taková, že i 2p2 + 1 je prvočíslo. Řešení. Zkusit začátek, pak p> p = 3k±l. Odtud 2p2 + 1 = 3(6k2 ± 4k + 1). □ 3.5. Dokažte: (a, b) — 1 =>• (a + 6, afe) = 1. Řešení. Sporem, (a, 6) = 1 A (a + 6, afe) ^ 1. Z druhého 3p : p|(a + 6) A p|afe. Z druhého (Euclid) p|aVp|6. Dohromady p\a A tj. p|(a, 6) = 1. □ 3.6. Dokažte: (a + 6, [a, b]) — (a, 6). Řešení. Lze převést na předchozí příklad, a :— ^f^y, & := JjTbj- n 3.7. Dokažte: a složené =>• a\(a — 1)!. Řešení. Nejprv zkusit pro malá a. Pak: a — b.c. Pokud b ^ c, pak 1 < b < c < a, a proto (a — 1)! — í..b..c..(a — 1), tj. a = 6c|(a — 1)!. Pokud b — c, tj. a = 62, pak z a = i2 > 4 plyne 6 > 2 a tedy i a — b2 > 2b, a proto (a — 1)! = 1..6..26..(a — 1). Odtud a = 62|(a- 1)!. □ Def. funkce vp. Pro a = p"1 • • -pf„k olí pokud p — pi vp(a) I 0 jinak Vlastnosti součin: vp{a.b) — vp{a) + vp{b) součet: vp{a + b) — vp{a), pokud vp{a) < vp(b) vp(a + b) > vp{a), pokud vp{a) — vp{b) gcd: vp((a, b)) = vp(a) lem: vp([a, b]) — vp(b) v obou případech vp{a) < vp(b) 3.8. Dokažte: (a, b) — 1 => (ab, c) — (a, c) • (b, c). Řešení, (a, b) = 1 =>• mín{vp(a), vp(b)} — 0. Odtud w.l.o.g. fp(0) = 1. Pak i vp{{a, c)) = 0 a tedy wp(L) = mm{í;p(6),í;p(c)} = □ 4. KONGRUENCE I. 3 3.9. Dokažte, že pokud y/ň G Q, pak "^/ň G N. Řešení. Předpoklad implikace říká, že existují r, s G N tak, že ^/ň = tj. n-sm — rm. Odtud vp(n) + m ■ vp(s) — m ■ vp(r), tj. m\vp(n). □ Minipísemka 3.10. Spočítejte GCD(728, 336 - 1, 345 - 1) a napište Bezoutovu rovnost. Řešení. 728 = 36 - 1 a proto GCD = 3(6-36-45) - 1 = 33 - 1 = 26. □ 3.11. Spočítejte GCD(4095, 242 - 1, 263 - 1) a napište Bezoutovu rovnost. Řešení. 4095 = 212 - 1 a proto GOD = 2(12-42-63) - 1 = 23 - 1 = 7. □ 4. Kongruence I. 4.1. Spočítejte zbytek po dělení čísla ab číslem m pro náhodně zvolené a,b,m. 4.2. Dokažte, že pro všechna k, m, n G N platí ll|55fe~K _|_ ^5m+2 _|_ c>5n Řešení. Spočítáme modulární mocniny čísel 3,4,5 a zjistíme 35 = 45 = 55 = 1 mod 11. Proto 55fe+1 + 45m+2 + 35™ = 51 + 42 + 3° = 22 = 0 mod 11. □ 4.3. Dokažte, že pro všechna a, b G Z platí a2 + b2 = 0 mod 3 ^> a = b = 0 mod 3. Řešení. Pokud a = 0, pak a2 = 0 a tedy i b2 = 0, tj. 6 = 0. Pokud a = ±1, pak a2 = 1, a proto 62 = —1, což není možné, (plyne i z malé Fermatovy věty) □ 4.4. Dokažte, že pro všechna a, b G Z platí a2 + 62 = 0 mod 7 ^> a = b = 0 mod 7. Řešení. Pokud a = 0, pak a2 = 0 a tedy i b2 = 0, tj. b = 0. Pokud a = ±1, ±2, ±3, pak a2 = 1, 4, 2, a proto 62 = 6, 3, 5, což není možné. □ 4.5. Nalezněte všechna n G N tak, že platí 3|n2™ + 1. Řešení. n2™ + l = n(—1)™ + 1 mod 3. Odtud buď n = 0 mod 2 a n = — 1 mod 3, nebo n = 1 mod 2 a n = 1 mod 3, tj. buď n = 2 mod 6 nebo n = 1 mod 6. □ 4.6. Dokažte, že lze po obvodu kružnice rozmístit čísla 1,2, ••• ,12 tak, aby libovolné tři sousední čísla a, b, c splňovaly 13\b2 — ac. Řešení. Rozmístíme popořadě čísla 21,22,-- - , 212 a uvážíme jejich zbytky po dělení 13. Pro tři sousední čísla 2fe~1, 2fe, 2fe+1 platí (2fe)2 - 2fe~1 • 2fe+1 = 0 a proto i jejich zbytky splňují b2 — ac= 0 mod 13. Zároveň mocniny 2 vygenerují celou zbytkovou třídu až na nulu, tj. právě čísla 1, 2, • • • ,12 (řád 2 modulo 13 je maximální, je to primitivní kořen). Dostáváme 2,4,8,3,6,12,11,9,5,10,7,1 □ 4.7. Úlohy o pokrytí... např. f{x, y) — 2x+3y mod 7 přiřadí každé celočíselné souřadnici nějaký zbytek modulo 7 a tím rovinu rozparceluje. Ukazuje to, že rovinu lze beze zbytku pokrýt všemi útvary, které vzniknou spojením sedmi čtverečků odpovídajícím různým zbytkům. 4 4.8. Odvoďte kritéria dělitelnosti čísly 2, 3, • • • ,11. Řešení. Univerzální kritérium — analýza zbytků mocnin 10fe. Např. pokud o, — «fc • • • «o — «o + «i ' 10 + • • • «fc • 10fe, pak 10 = —1 mod 11 dá a = ciq — a,\ + ■ ■ ■ + (—l)kcik mod 11. Modulo 7 dostaneme 10° = 1, 101 = 3, 102 = 2, 103 = -1, 104 = -3, 105 = -2, 106 = 1. Odtud a = ao + 3ai + 2a^ — — 3a4 — 2a$ + atd. mod 7. □ 5. Eulerova funkce 5.1. Spočítejte Eulerovu funkci ip(n) pro n — 180, 636,1000,1001. Řešení. ^(180) = <^(22.32.5) = 2(2 - 1).3(3 - 1).(5 - 1) = 48. Podobně ^(635) = 504, v?(1000) = 400, v?(1001) = 720. □ 5.2. Vyřešte rovnici (p(3x5y) — 600. Řešení. tp(3x5y) = 2.32;"1.4.5^1 pro x,y > 1. Odtud x = 2, y = 3. □ 5.3. Vyřešte rovnici (p(m) — 6. Řešení. Pokudp|m, pakp-í\(p(m). Odtud m = 2x3y7z, tedy 1. Diskuze dělitelnosti dá x, y < 2 a z < 3. Dalším rozborem dostaneme z — í,y — 0,x — 0, z — í,y — 0,x — 1, z — 0,y — 2,x — 0 a z = l,y = 2,x = 1, tj. m = 7,14,9,18. □ 5.4. Vyřešte rovnici ip(m) — 14. Řešení. 8 a 15 jsou složená, proto 72|m a tedy 6.7 — 42\(p(m). Žádné řešení neexistuje. □ 5.5. Vyřešte rovnici (p(m) — y. Řešení. Především y e Z. Položme m — 2at, kde 2 { í a a > 1. Pak (p(m) — 2a-1(p(t). Tedy v?(í) = t, tj. í = 1. Řešení je m = 2a pro a > 1. □ 5.6. Vyřešte rovnici ip(m) — y. Řešení. Položme m — 3aí, kde (3, ť) — 1 a a > 1. Pak y(m) = 3a_1.2.(p(t). Tedy V?(í) = |. Z minulého příkladu víme t — 2b. Řešení je m — 3a2b pro a, b > 1. □ 5.7. Vyřešte rovnici ip(pm) — (p(m). Řešení. Pokudp|m, pak ip(pm) — pip(m) a pokudp{ to, pak ip(pm) — (p—l)ip(m). Řešením je p — 2, to liché. □ 6. Eulerova věta 6.1. Jaký zbytek dává a100 po dělení číslem 125? Řešení. Platí y(125) — 52(5 — 1) — 100, a proto pro libovolné a nesoudělné s 5 je aioo = i mod 125. Pokud 5|a, pak 125|a100, tj. a = 0 mod 125. □ 6.2. Dokažte 2341 = 2 mod 341. Řešení. 341 = 11.31. Podle Eulerovy věty platí 210 = 1 mod 11 a 230 = 1 mod 31. Proto 2341 = 2 mod 11 a 2341 = 211 = 2 mod 31. □ 6.3. Určete poslední cifru čísla 37 373 . Řešení. Platí ip (10) = 4a 3737 = 1 mod 4. Proto 373?37 = 37 = 7 mod 10. □ 7. LINEÁRNÍ KONGRUENCE 5 6.4. Určete poslední dvě cifry čísla 72014. Řešení. Platí y>(100) = 40 a (7,100) = 1. Proto podle Eulerovy věty platí 740 = 1 mod 100. A protože 2014 = 14 mod 40, je 72014 = 714. Dále máme 73 = 343 = 43 mod 100 a 74 = 43.7 = 301 = 1 mod 100, a proto 72014 = 714 = 72 = 49. □ 6.5. Dokažte, že číslo 22*"+1 + 7 je složené. Řešení. Vyzkoušíme, jaké zbytky dává mocnina čísla 2 modulo malá prvočísla. Zjistíme, že modulo 11 máme 210 = 1. Zároveň jsou zbytky mocnin 2 modulo 10 periodicky 2,4,8,6, tj. 24n+1 = 2 mod 10. Odtud 224"+1 + 7=22 + 7=ll = 0 mod 11. □ Minipísemka 6.6. Vyřešte nerovnici (p(n) < 6. Řešení. Prvočísla p\n musí splňovat p— l\ip(n) G {1, 2, 4} (ip(n) nemůže být liché). Odtud n — 2x3y5z. Pro (p(n) — 1 je pouze n — 1 nebo n — 2, pro (p(n) — 2 je z — 0 & x,y < 1, tj. n — 3 nebo n — 6. Pro x = 2915 = 1215 mod 17. (b) Bezout: Z Euklida 1 = 12.17-7.29, tj. -7.29 = 1 mod 17, a proto x = -7 = 10. (c) Ad hoc: 12x = 1 = 18 mod 17, tj. 2x = 3 = 20, tj. x = 10 mod 17. □ 7.3. Vyřešte Ux = 23 mod 31. Řešení. Z Bezouta 1 = 5.31 - 11.14, tj. x = 23.(-11) = -5. Ad hoc: 14x = -8, tj. 7x = -4 = -35, tj. x = -5 mod 31. □ 7.4. Vyřešte 6x = 27 mod 12. Řešení. (6,12) — 6 { 27. Nemá řešení. □ 7.5. Vyřešte 8x = 20 mod 12. Řešení. Vydělením dostaneme ekvivalentní kongruenci 2x = 5 mod 3, tj. x = 1 mod 3. Modulo 12 pak jsou 4 řešení x = 1,4, 7,10. □ 6 8. Soustavy lineárních kongruencí 8.1. Vyřešte x = 2 mod 5 x = 8 mod 11 Řešení, (a) Pomocí čínské zbytkové věty x = 2.11.[11]^1 + 8.5.[5]^ mod 55. Pomocí Bezouta a Euklida zjistíme inverze [ll]^1 — 1, [5\ii — 9, tj. x = 22 + 360 — 382 = -3 mod 55. (b) Ad hoc: Z první kongruence x — 5í + 2 dosadíme do druhé 5í + 2 = 8 mod 11, tj. 5í = 6 = —5 mod 11, tj. x = — 1 mod 11. Dosadíme zpět: x — 5(lls — 1) + 2 — 55s - 3. □ 8.2. Vyřešte Ax — 3 mod 7 bx = 4 mod 6 Řešení, x = 20 mod 42. □ 8.3. Vyřešte 2x = a mod 4 3x = 4 mod 10 Řešení. 4 { a nemá řešení, pokud 4|a, pak x = —2 mod 10. □ 8.4. Vyřešte 3x = 5 mod 7 2x = 3 mod 5 3x = 3 mod 9 Řešení. Třetí kongruence je ekvivalentní x = 1 mod 3, tj. x — 3í + 1. Dosazením do druhé: 2(3í+l) = 3 mod 5, tj.í=l mod 5, tj. t = 5s + l, tj. x = 3(5s + l) + l = 15s + 4. Dosazením do první: 3(15s + 4) = 5 mod 7, tj. 3s = 0, tj. s — Ir. Celkem x — 15.Ir + 4, neboli x = 4 mod 105. □ 8.5. Piráti se hádají o mince ~> x = 10 mod 13 x = 3 mod 12 x = 0 mod 11 Řešení, x = 231 mod 11.12.13. □ 8.6. Počítání vojáků pomocí čtverců. Např. x — 55863 vojáků lze modulárně reprezentovat pomocí čtverců 5x5, 7 x 7 a 9 x 9 jako x = 13 mod 25 x = 3 mod 49 x = 54 mod 81 Řešení, x = 55863 mod 25.49.81. □ 9. BINOMICKÉ KONGRUENCE, PRIMITIVNÍ KOřENY 7 8.7. CRT reversed: Vyřešte lineární kongruenci 3446x = 8642 mod 208. Řešení. Vydělením dvěma: 1723x = 4321 mod 104. Rozděláme na soustavu podle faktorů modulu, tj. 104 — 8.13 a dostaneme 3x = 1 mod 8 7x = 5 mod 13. Tu vyřešíme a dostaneme x = 75 mod 104. □ 9. Binomické kongruence, primitivní kořeny 9.1. Vyřešte kongruenci x5 = 10 mod 11. Řešení. Výčtem: X 0123456789 10 xb - 10 mod 11 1202220002 0 Mocniny g — 2 generují celou zbytkovou třídu (bez 0): k 0123456789 10 2k mod 11 124 28 5 10 9736 1 a proto x5 — 10 mod 11 je ekvivalentní 25Xa = 25 mod 11 a to je ekvivalentní bxa = 5 mod 10. Tato lineární kongruence je ekvivalentní kongruenci xa = 1 mod 2, tj. řešením dané kongruence jsou x = 21, 23, 25, 27, 29, tj. x = 2, 8,10, 7, 6. □ 9.2. Najděte primitivní kořeny modulo 23. Řešení. Protože cp(23) — 22 — 2.11, tak stačí testovat g2 a g11. 9 2 3 4 5 6 7 8 9 10 11 12 13 g2 mod 23 4 9 16 2 13 3 18 12 8 6 6 8 g11 mod 23 1 1 1 -1 1 -1 1 1 -1 -1 1 1 9 14 15 16 17 18 19 20 21 22 g2 mod 23 12 18 3 13 2 16 9 4 1 g11 mod 23 -1 -11-11 -1 -1 -1 -1 Primitivní kořeny jsou g = 5, 7,10,11,14,15,17,19, 20, 21, 22. □ 9.3. Dokažte neexistenci primitivních kořenů modulo 8. Řešení. Protože cp(8) — 4 tak stačí testovat g2. Uděláme ale celou tabulku X 3 5 7 x2 mod 8 1 1 1 x3 mod 8 3 5 7 x4 mod 8 1 1 1 Všechna nesoudělná čísla dávají v druhé mocnině jedničku. □ 9.4. Najděte nejmenší primitivní kořen modulo 41 a vyřešte kongruenci 7x17 = 11 mod 41. Řešení. Protože cp(41) — 40 tak stačí testovat gs a g20: 9 2 3 4 5 6 gH mod 8 10 1 18 18 10 g20 mod 8 1-11 1-1 Máme tedy g — 6. Kongruenci upravíme na x17 = 25 mod 41 a zjistíme 25 = 64, tj. ekvivalentní kongruence je 17xa = 4 mod 40. Tu rozdělíme podle faktorů modulu na soustavu xa = 4 mod 8 a 2xa = 4 mod 5. Ta má řešení xa = 12 mod 40, a proto x = 612 = 4 mod 41. □ 8 9.5. Najděte nejmenší primitivní kořen modulo 17 a vyřešte kongruenci x4 — 8 mod 17. Řešení. Zjistíme g — 3. 8 — 310, a proto máme 4xa = 10 mod 16. Tato kongruence ale nemá řešení, protože (4,16) — 4 \ 10. Lze vidět i přímo z kritéria pro řešitelnost binomické kongruence: 816/4 — 84 = —1 mod 17. □ 10. Kvadratické kongruence 10.1. Mějme kongruenci x2 = 271 (mod 323). Zjistěte, jestli má řešení a kolik a pak řešení najděte. Přezkoumejte řešitelnost pomocí Legenreova symbolu. Řešení. Zjistíme 323 — 17 • 19. Odtud dostaneme ekvivalentní soustavu: x2 = 271 = -1 (mod 17) x2 = 271=5 (mod 19). 17-1 19-1 Pro první je (—1) 2 =1, pro druhou 5 2 — 59 = 1 (mod 19). Každá kongruence má tedy právě dvě řešení, tj. zadaná kongruence má čtyři řešení. Primitivní kořen pro 17 je g — 3 (testujeme gs), pro 19 je g — 2 (testujeme ge a g9). Přitom — 1 = 38 (mod 17) a 5 = 216 (mod 19). Soustava je tedy ekvivalentní soustavě 32x* = 38 (mod 17) 22xb =216 (mod 19), kde x = 3X" (mod 17) a i e 2x" (mod 19), tj. 2xa = 8 (mod 16) a 2xb = 16 (mod 18). Odtud x = 34 ee 13 nebo x = 312 ee 4 (mod 17) a x = 28 ee 9 nebo x = 217 ee 10 (mod 19). Z Euklidova algoritmu dostaneme Bezoutovu rovnost 1 — 9.17— 8.19, a proto je řešenízadané kongruence x = 9.17.(9 nebo 10) — 8.19.(13 nebo 4), tj. x ee 47,123, 200 nebo 276 (mod 323). □ Legendreův symbol. Ověření řešitelnosti kvadratické kongruence bez počítání modulární mocniny. Definice :— — ±1. Vlastnosti: ~~ ^ a^ ''h a = b = —1\ / „N£=i |l p ee 1 (mod 4) l - (-1) 2 = ) těžší je dokázat p J -1 pE-1 (mod 4) 2\ ^ [l p = ±l (mod 8) p) { ' 1-1 pEE±3 (mod 8) a kvadratickou reciprocitu P\ ^ p — 1 (mod 4) nebo q — 1 (mod 4) 1J \PJ ' I-(f) jinak V minulém příkladě ihned dostáváme (jf) — 1 a (^) = (^p) — (-jp) = 19+1 1. Protože 5^~~ = 5 a 4|19 + 1, můžeme hned napsat řešení druhé kongruence ±5^ = ±55 = ±9. 10.2. Nalezněte všechna x taková, že x2 ee 7 (mod 43). Řešení. (^) — — (42) — — (i) — —1. Kongruence nemá řešení. □ 10.3. Má kongruence x2 = 79 (mod 101) řešení? Řešení. (^) = (^) = (ff) = (£) (#) = (£)=- (§) = (£) = 1. Kongru-ence má řešení. □ MINIPÍSEMKA 9 Jacobiho symbol. Zobecnění Legendreova. Ty samé vlastnosti, nemusí být prvočísla. Je-li symbol 1, pak řešení může i nemusí existovat. 10.4. Má kongruence x2 = 38 (mod 165) řešení? Řešení. Spočítáme nejdřív Jacobiho symbol: (j^) — (jf^) (xifg) — ~ (t§s) ~ (W) ľ - (i) = - (i) = -(&) = . (ň) .(#) - (é) - (¥) = (l) = i- řešení může i nemusí existovat. Spočteme jednotlivé Legendrovy symboly. Kongruence je ekvivalentní soustavě x2 = 38 = 2 (mod 3) x2 = 38 = 3 (mod 5) x2 = 38 = 5 (modli). Symboly jsou (§) = -1 (§) = (§) = (§) = 1 a (A) = (f) (I) = 1. Vidíme, že dvě z těchto tří kongruencí nemají řešení, a proto i zadaná kongruence není řešitelná. □ 10.5. Spočtěte pomocí Legendrových symbolů a pomocí Jacobiho symbolu. Řešení. L: Potřebujeme faktorizovat! 1001 — 7.11.13, 9907 je prvočíslo. — ( 7 \ / 11 \ ( 13 \ ( 7 \ _ _ f 9907^ _ _ (2\ _ i / U \ _ _ f 9907\ _ V9907/ V9907/ V9907/' V9907/ V 7 / \7 ) ' V9907/ Vil/ - (£) = (¥) = (I) = 1 a (M = (W) = (ě) = 1- Dohromady (§§) = -1. J: Nepotřebujeme faktorizovat! «) = (f§2Z) = (JgjjL) = (_2_) (^) = = f 1001N _ /ÍČKA _ /449\ _ í_37_\ _ /"ltm _ r29\ _ f37\ _ /_8_\ _ ( _2_\3 _ _-, n v 449 / v 449/ v 103/ v 103/ v 37/ v 37/ v 29/ v 29/ v 29/ ~~ lm Použití. Rabínův kryptosystém, Euler-Jacobiho test prvočíselnosti. Fermatův test N: aN^ = 1 (mod N), Euler-Jacobiho test N: = (■§■). Ab- solutní Fermatova pseudoprvočísla — Carmichaelova čísla - projdou Fermatovým testem pro každou bázi a. Korseltovo kritérium: p2 \ N Carmichaelovo právě tehdy, když p\N =^ p - Í\N - 1. 10.6. Ukažte, že 2465 je Carmichaelovo číslo. Řešení. 2465 = 5.17.29 a 4,16, 28|2464. Podle Fermatovy věty pak a2464 = (a616)4 = 1 (mod 5), a2464 = (a164)16 = 1 (mod 17) a a2464 = (a88)28 = 1 (mod 29), tj. a2464 = x (mod 5_17_29 = 2465). □ 10.7. Ukažte, že 341 je Fermatovo pseudoprvočíslo o základu 2 a není Euler-Jacobiho pseudoprvočíslo o základu 2. Ukažte, že 561 je E-J pseudoprvočíslo o základu 2. (pozn.: tyto pseudoprvočísla jsou nejmenší o daném základu) Řešení. 210 = 1 (mod 341) Proto 2340 = 1 (mod 341) i 2170 = 1 (mod 341). Zároveň ale (gfj) = -1. Pro 561 máme 2280 = 1 (mod 561) = 1 a (^j) = 1. □ 10.8. Prolomte šifru ElGammal. Honza zveřejnil klíč (53,2,19) a přijal od Martina šifru (2,16). Jakou zprávu mu Martin poslal? Řešení. Potřebujeme zjistit Honzův soukromý klíč h. Ten je dán diskrétním logaritmem, 2h = 19 (mod 53). Počítejme tedy modulární mocniny dvojky modulo 53. Zjistíme 211 = -19 (mod 53). Protože (^) = -1, je 226 = -1 (mod 53) a tedy 237 = 19 (mod 53), tj. h — 37. Tím je šifra prolomena a protože 19_1 = 14 (mod 53), je zpráva 14 • 16 = 47 (mod 53). □ Minipísemka 10.9. Je řešitelná kongruence x2 = 72 (mod 1219)? 2-) = = (-1) f_3_^ 19/ V1219/ V1219/ v ) V1219/ Řešení, (jjfg) — (l^fg) (T2I9) ~ (—1) (12I9) ~ — 1- Kongruemce nemá řešení. □ 10 10.10. Je řešitelná kongruence x2 = 14 (mod 1363)? Řešení. (^) = (^) (^) = (-1) • (-1) (if2) = (f) = (I) = (|) = -1. Kongruemce nemá řešení. □ 11. Kódování