Diskrétní matematika - cvičení 4. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Príklad _i Určete primitivní kořen modulo 41. J Řešení i Protože je 41 prvočíslo, máme 38 = ^ Vidíme, že řád čísla 3 je 8 (menší být opravdu nemůže, dokažte to z diagramu dělitelů) a nejedná se o primitivní kořen modulo 41. Príklad_ _i Určete primitivní kořen modulo 41. 1 Řešení i Číslo a = 4 zkoušet nemusíme, neboť 410 = 220 = 1 a má tedy řád maximálně 10. Obecně mocnina čísla, které není primitivním kořenem, nemůže být primitivním kořenem. Pokračujeme s a = 5: počítáme 51 = 5, 52 = 25, 54 = 10, 58 = 18, 516 = 37, takže 520 = 516 • 54 = 37 • 41 = 1, 58 = 18. Vidíme, že řád čísla 5 je 20, případně ještě menší a nejedná se o primitivní kořen modulo 41. Příklad Určete primitivní kořen modulo 41 Řešení Pokračujeme s a = 6 = 2 • 3, proto 620 = 220 . 320 = x . = _1? 6« = 2« . 3tí = 10 • 1 = 10 Konečně jsme našli primitivní kořen 6 modulo 41. 8 _ o8 08 _ Příklad 1 Určete všechny primitivní kořeny modulo 41. 1 1 Řešen í_1 Protože je 6 primitivní kořen, jsou všechny zbytky 6°,6\62,...,639 různé (a 6° = 640), zároveň jsou nesoudělné s 41 a je jich V?(41) = 40, takže tvoří redukovanou soustavu zbytků, tj. jedná se právě o všechny zbytky 1,... ,40. Můžeme proto primitivní kořeny hledat mezi těmito čísly. 6° = 1 má řád 1, 61 má řád 40, přesuňme se tedy k 62. ' Příklad _i Určete všechny primitivní kořeny modulo 41. 1 Řešení _i Zjevně (62)20 = 640 = 1, takže 62 určitě nebude primitivním kořenem (ve skutečnosti má řád přesně 20), podobně například (615)8 = (63-5)8 = 63.40 = L Mělo by být víceméně jasné, že kdykoliv ar bude mít exponent r soudělný s 40, bude jeho řád menší než 40: buď bude exponent r dělitelný 2 a pak (ar)20 = a^'40 = 1 nebo bude exponent r dělitelný 5 a pak (ar)8 = aH° = 1. Příklad Určete všechny primitivní kořeny modulo 41. 1 Řešení Naopak ar bude primitivní kořen, pokud (r, 40) = 1 , demonstrujme to na r = 3, tedy zkoumejme mocniny čísla a3, které dávají zbytek (a3)5 = a3s = a° = 1 ^ 40 3s ^ 40 s. V poslední ekvivalenci se využívá nesoudělnost 40 a 3, pomocí kongruencí je to nám dobře známé 3s = 0 s = 0 (mod40). Príklad Určete všechny primitivní kořeny modulo 41 Řešení Každopádně vidíme, že řád a3 je vskutku 40 a jedná se o primitivní kořen, podobně všechna čísla ar, kde r je nesoudělné s 40; jsou to tedy právě: .1 .3 .7 .9 .11 .13 .17 .19 .21 .23 .27 .29 .31 .33 .37 .39 cijCljCljCljCl j a j a ^ d ^ d ^ d ^ d ^ d ^ d ^ d ^ d ^ d Samozřejmě víme, že jich je ^(40) = 102x = 150 = 82 102x = 82 130x = 150 —~1J > 28x = 68 Príklad Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod232). Řešení 102x = 82 28x = 68 -311 » 18x = -122 = 110 28x = 68 -í-i 18x = 110 lOx = -42 —lil ■> 8x = 152 = -80 lOx = -42 -í-i 8x = -80 -4-II ■>0x = -232 = 0 2x = 38 2x = 38 Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod232). Řešení Původní rovnice a tedy i původní soustava je ekvivalentní soustavě 2x = 38 (mod232) Ox = 0 (mod 232) Druhá rovnice je zbytečná, první rovnici lze vydělit koeficientem u x - celou včetně modulu! (Ani jedno nemusí být pravda v případě, kdy původní rovnice nemá řešení, viz dále!) Dostáváme tak ekvivalentně x= 19 (mod 116) Přehledněji lze psát takto, kde všechny po sobě jdoucí dvojice rovnic jsou ekvivalentní: 232x = 0 130x = 150 102x = 82 28x = 68 18x = 110 lOx = -42 8x = -80 2x^38 (mod232) ^ x = 19 (mod 116) Ox = 0 Poznámka Že je potřeba počítat až do konce si demonstrujeme na dvou jednoduchých příkladech, prvně 4x = 1 (mod 10): lOx = 0 4x = 1 2x = 8 (mod 10) O x = A (mod 5) Ox = 5 Bez posledního řádku bychom se mohli mylně domnívat, že x = 4 (mod 5) je řešením. V jiném případě 4x = 1 (mod 14) dostaneme podobně: 14x = 0 4x= 1 2x = 11 (mod 14) 0x = 7 V tomto případě dokonce předposlední rovnici vydělit dvěma nelze. Poznamenejme, že pokud je poslední rovnost splněna, lze předposlední rovnici vždy vydělit (to plyne z teorie, nebudeme to dále rozebírat). Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod232). Řešení Řešením je tedy jediná zbytková třída modulo 116, zabývejme se ještě krátce počtem řešení jakožto zbytkových tříd modulo 232, stejně jak je formulováno zadání. Ve zbytkových třídách modulo 232 se zbytkové třídy modulo 116 vyskytnou každá dvakrát: 0 1 -v 116 115 116 117 -v 116 231 = 0 1 ... 115 0 1 ... 115 116 116 232 232 Zbytková třída 19 (mod 116) tedy odpovídá dvěma zbytkovým třídám 19 (mod 232) a 19 + 116 (mod 232). To jsou dvě řešení původní úlohy. Vyřešte soustavu kongruencí x = 7 (mod27) x = —3 (mod 11) Řešení Podobně jako na konci posledního příkladu dá 7 (mod 27) jedenáct zbytkových tříd modulo [27,11] = 27 • 11 = 297, konkrétně 7,7 + 27,7 + 2-27, ...,7 + 10-27. Obdobně zbytková třída —3 = 8 (mod 11) dá dvacet sedm zbytkových tříd 8,8+11,8 + 2-11,...,8 + 26-11. Príklad Vyřešte soustavu kongruencí x = 7 (mod 27) x = -3 (modli) Řešení Na těchto seznamech je právě jedno číslo společné a to je řešením úlohy. Tento postup je však velmi nepraktický (exponenciální časová složitost). O něco lepší je počítat podobně jako v případě jedné rovnice - prvně převedeme obě kongruence na společný modul [27,11] = 27 • 11 = 297: llx = 77 27x = -81 (mod 297) (mod 297) a nyní postupným upravováním vyřešíme. Vyřešte soustavu kongruencí x = 7 x = -3 (mod 27) (modli) Řešení 27x = -81 (mod 297) llx = 77 (mod 297) 5x^-235 = 62 (mod 297) x = -47 = 250 (mod 297) Nevýhodou je počítání s relativně velkými čísly (řádově 297); vhodnou modifikací lze počítat s čísly menšími (řádově 27 a 11) tím, že pravou stranu zapisujeme jako kombinaci 27 a 11: Vyřešte soustavu kongruencí x = 7 x = -3 (mod 27) (modli) Řešení 27x = -3 • 27 (mod 297) 11* = 7-11 (mod 297) 5x = -3-27-14-ll (mod 297) x = 6 • 27 + 35 • 11 = 6 • 27 + 8 • 11 = 250 (mod 297) (protože je 27 • 11 = 0, lze koeficienty u 27 redukovat modulo 11, resp. koeficienty u 11 redukovat modulo 27). O něco přímočařejší a podobně efektivní je substituční metoda. Vyřešte soustavu kongruencí x = 7 (mod27) x = —3 (mod 11) První kongruence x = 7 (mod 27) má řešení právě x = 27ř + 7, to dosadíme do druhé kongruence a vyřešíme vzhledem k t: 27ř + 7 = -3 5í = 1 t = 9 (modli) (modli) (modli) Vyřešte soustavu kongruencí x = 7 (mod 27) x = —3 (mod 11) Řešení Opět můžeme psát t = lis + 9 a toto dosadíme do prvního vyjádření: x = 27r + 7 = 27 • (lis + 9) + 7 = 297s + 250 To je již řešením soustavy (v "parametrickém tvaru"), lze jej samozřejmě zpětně zapsat jako kongruenci x = 250 (mod 297). Vyřešte soustavu kongruencí x = 1 (mod 10) x = 5 (mod 18) x = -4 (mod 25) Řešení Vyřešíme posledním způsobem: z první rovnice máme x = 10ŕ + 1, dosadíme do druhé, dostaneme 10r + 1 = 5 (mod 18), tj. 10r = 4 (mod 18) a vyřešíme vzhledem k ŕ: Vyřešte soustavu kongruencí x = 1 x = 5 x = -4 Řešení 18ř = 0 lOt = 4 8t = -4 2t = 8 (modl8) Oř = 0 (mod 10) (mod 18) (mod 25) 4» t = 4 (mod 9) Tedy t = 9s + 4 x = lOř + 1 = 10 • (9s + 4) + 1 = 90s + 41. Vyřešte soustavu kongruencí x = 1 x = 5 x = -4 (mod 10) (mod 18) (mod 25) ■v Řešení ■v Řešením soustavy prvních dvou kongruencí je x = 90s + 41, to dosadíme do třetí kongruence: 90s + 41 = —4 (mod 25), tj. 15s = 5 (mod 25) a opět vyřešíme vzhledem k s. 25s = 0 15s = 5 lOs = 20 5s = 10(mod25) <^> s = 2 (mod 5) Os = 0 Příklad Vyřešte soustavu kongruencí x = 1 (mod 10) x = 5 (modl8) x = -4 (mod 25) I I Máme s = 2 (mod 5), tj. s = 5r + 2 a dosazením získáme x = 90s + 41 = 90 • (5r + 2) + 41 = 450r + 221 nebo ekvivalentně x = 221 (mod 450). Príklad Řešte kongruenci 23941x = 915 (mod 3564) Rešení Lze řešit standardně, ale čísla budou vycházet velká. Alternativně rozložme 3564 = 4-81-11 na součin prvočíselných mocnin a počítejme příklad prvně modulo 4, 81, 11 a na závěr dejme výsledky dohromady pomocí CRT. x = 3 (mod 4) 46x = 24 (mod 81) 5x = 2 (modli) x = 3 (mod 4) x = -3 (mod 81) x = 7 (mod 11) Začneme řešit od nejmenšího modulu: x = 4t + 3 dosadíme do poslední kongruence: 4r + 3 = 7 (mod 11), tj. 4t = 4 (mod 11) má zjevně řešení t = 1 (mod 11), takže ŕ = lis + 1, tj. x = 44s + 7 a dosadíme do druhé kongruence: 44s + 7 = —3 (mod 81), tj. 44s = —10 (mod 81) a vyřešíme vzhledem k s. Řešte kongruenci 23941x = 915 (mod 3564). 81s = 0 44s = -10 37s = 10 7s = -20 2s = 29 ls = 55 (mod 81) Os = 0 Dosazením x = 44s + 7 = 44 • (81r + 55) + 7 = 3564r + 2427, tj. x = 2427 (mod 3564).