Diskrétní matematika - cvičení 4. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Příklad Určete primitivní kořen modulo 41 Príklad _i Určete primitivní kořen modulo 41. J Řešení i Protože je 41 prvočíslo, máme v?(41) = 41 — 1 = 40 a řád každého čísla dělí 40: 40 □ ÉJ1 Príklad _i Určete primitivní kořen modulo 41.J Řešení i Protože je 41 prvočíslo, máme v?(41) = 41 — 1 = 40 a řád každého čísla dělí 40: 40 8 20 10 Hledáme číslo a řádu 40. Podle Eulerovy věty a40 = 1, budeme kontrolovat, zda a20 ^ 1, a8 ^ 1. Příklad _i Určete primitivní kořen modulo 41. J Řešení 40 8 20 Platí totiž: jestliže řád a není 40, pak a = 1 nebo a = 1. >0 Q,o Určete primitivní kořen modulo 41. Řešení 40 8 20 Platí totiž: jestliže řád a není 40, pak a u = 1 nebo 3ľ = 1. Obecně je potřeba testovat mocniny s exponentem (p(m)/p, kde p je prvočíslo dělící (p(m), v našem případě v?(41) = 40 = 23 • 5, proto se testují exponenty 40/2, 40/5. Příklad Určete primitivní kořen modulo 41. Protože 3=1 má řád 1, začneme s a = 2: Příklad Určete primitivní kořen modulo 41 Řešení Protože a = 1 má řád 1, začneme s a = 2: počítáme 21 = 2, 22 = 4, 24 = 16, 28 = 256 = 10 a konečně 216 = 100 = 18, □ ^ > 4 ^ >■ 4 .= >0 0,0 Příklad Určete primitivní kořen modulo 41 Řešení Protože a = 1 má řád 1, začneme s a = 2: počítáme 21 = 2, 22 = 4, 24 = 16, 28 = 256 = 10 a konečně 216 = 100 = 18, takže 220 = 216 • 24 = 18 • 16 = 1, 2° = 10. 8 _ □ ^ > 4 ^ >■ 4 .= >0 Q,o Určete primitivní kořen modulo 41. Protože a = 1 má řád 1, začneme s a = 2: počítáme 21 = 2, 22 = 4, 24 = 16, 28 = 256 = 10 a konečně 216 = 100 = 18, takže 220 = 2i6 . 24 = 18 ■ 16 = 1, 28 = 10. Vidíme, že řád čísla 2 je 20, případně ještě menší a nejedná se o primitivní kořen modulo 41. Určete primitivní kořen modulo 41. ■v Řešení Pokračujeme s a = 3: počítáme 31 = 3, 32 = 9, 34 = 81 = -1, 38 = 1, 316 = 1, ta kže 320 = 3I6 . 34 = _x> 38 = 1 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. □ rjfl ► < ► 4 = 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 i _ 5A = 5, 52 = 25, 54 = 10, 5° = 18, 51U = 37: 8 _ 16 _ takže 520 = 516 • 54 = 37 • 41 = 1, 5° = 18 8 _ Vidíme, že řád čísla 5 je 20, případně ještě menší a nejedná se o primitivní kořen modulo 41. □ rS> ► < ► •< = 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 Určete všechny primitivní kořeny modulo 41 Príklad Určete všechny primitivní kořeny modulo 41 Řešení Protože je 6 primitivní kořen, jsou všechny zbytky 6°,6\62,...,6 39 různé (a 6° = 640), Určete všechny primitivní kořeny modulo 41. Řešení Protože je 6 primitivní kořen, jsou všechny zbytky 6°,6\62,...,6 39 různé (a 6° = 640), zároveň jsou nesoudělné s 41 a je jich y>(41) = 40, Určete všechny primitivní kořeny modulo 41. Řešení 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. Určete všechny primitivní kořeny modulo 41. Řešení 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 Určete všechny primitivní kořeny modulo 41 3 Řešení Zjevně (62)20 = 640 = 1, takže 62 určitě nebude primitivním kořenem (ve skutečnosti má řád přesně 20), ' 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 Určete všechny primitivní kořeny modulo 41 Řešení 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: Príklad Určete všechny primitivní kořeny modulo 41 Řešení 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. >0 0,0 Příklad Určete všechny primitivní kořeny modulo 41 Ř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 1: (a3)5 = a3s = a° = 1 ^ 40 | 3s ^ 40 s. 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). Určete všechny primitivní kořeny modulo 41. 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) = 18x = -122 = 110 28x = 68 28x = 68 -í-i 18x = 110 -MI ■> 8x = 152 = -80 lOx = -42 lOx = -42 -í-i 8x = -80 -4-II ■>0x = -232 = 0 2x = 38 2x = 38 Príklad Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod 232) Řešení Původní rovnice a tedy i původní soustava je ekvivalentní soustavě 2x = 38 (mod 232) 0x = 0 (mod 232) Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod232). 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! 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!) Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod 232). Řešení Původní rovnice a tedy i původní soustava je ekvivalentní soustavě 2x = 38 (mod 232) 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) Řešení 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 Ox = 0 & x = 19 (modll6) >0 Q,o 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) Ox = 7 V tomto případě dokonce předposlední rovnici vydělit dvěma nelze. Poznámka V jiném prípade 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). Příklad Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod 232) Ř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í. Příklad Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod 232) Ř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 115 116 117 >0 o,o Příklad Spočtěte nějaké jednoduché lineárních kongruence, např. 130x = 150 (mod 232) Ř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 ... 231 -v 116 0 1 ... 115 0 1 ... 115 -v 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. Příklad Vyřešte soustavu kongruencí x = 7 (mod 27) x = -3 (modli) Ř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. >0 Q,o 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). Vyřešte soustavu kongruencí x = 7 x = -3 (mod 27) (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: Příklad Vyřešte soustavu kongruencí x = 7 (mod27) x = —3 (mod 11) Řešení 27x = -3 • 27 (mod 297) llx= 7-11 (mod 297) 5x = -3 • 27 - 14 • 11 (mod 297) x = 6 • 27 + 35 • 11 = 6 • 27 + 8 • 11 = 250 (mod 297) Príklad Vyřešte soustavu kongruencí x = 7 (mod 27) x = -3 (modli) Řešení 27x llx 5x x -3-27 7 • 11 -3-27-14-11 6 • 27 + 35 • 11 = 6 • 27 + 8 • 11 = 250 (mod 297) (mod 297) (mod 297) (mod 297) (protože je 27 • 11 = 0, lze koeficienty u 27 redukovat modulo 11, resp. koeficienty u 11 redukovat modulo 27). Vyřešte soustavu kongruencí x = 7 x = -3 (mod 27) (modli) Řešení 27x = -3 • 27 llx= 7-11 5x = -3 • 27 - 14 • 11 x = 6 • 27 + 35 • 11 = 6 • 27 + 8 • 11 = 250 (mod 297) (mod 297) (mod 297) (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 (modli) 5t = l (modli) t = 9 (modli) Vyřešte soustavu kongruencí x = 7 (mod27) 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 = 27t + 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). Príklad_ Vyřešte soustavu kongruencí x = 1 (mod 10) x = 5 (modl8) x = -4 (mod 25) 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 ŕ: Příklad 1 Vyřešte soustavu kongruencí x = 1 (mod 10) x = 5 (modl8) x = -4 (mod 25) Řešení 18ř = 0 lOt = 4 8t = -4 2t = 8 (mod 18) Oř = 0 O t = 4 (mod 9) Tedy t = 9s + 4 x = lOt + 1 = 10 • (9s + 4) + 1 = 90s + 41. Příklad Vyřešte soustavu kongruencí x = 1 (mod 10) x = 5 (modl8) x = -4 (mod 25) Ř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 (mod 25) Os = 0 s = 2 (mod 5) OQ.O Příklad Vyřešte soustavu kongruencí x = 1 (mod 10) x = 5 (modl8) x = -4 (mod 25) Řešení 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) 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) Príklad Řešte kongruenci 23941x = 915 (mod3564). 1 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) x = 3 (mod 4) 46x = 24 (mod 81) x = -3 (mod 81) 5x = 2 (mod 11) 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, 9 0, o 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).