asked Nov 23 '14
Mohl by mi prosím někdo vysvětlit, jak se řeší tenhle příklad?
Vyberte podmínku pro číslo x tak, aby postihla všechna řešení kongruence 32x = 40(mod 56):
a) x = 10(mod 56)
b) x = 10(mod 7)
c) x = 10(mod 14)
d) ani jedna z možností
e) x = 3(mod 28)
Správně má být b), odhadem bych řekla, že to bude mít něco společného s tím, že platí 56|7 i 40|10, ale nějak vůbec nechápu, jak se takový typ příkladů obecně řeší.
answered Nov 23 '14
Viz přednáška o lineární kongruenci (přednáška 7, strana 15, 16).
32x \equiv 40 (\mod{56}) \gcd{(32, 56)} = 8 8|40 \Rightarrow \text{rovnice má řešení a platí} \frac{32}{8}x \equiv \frac{40}{8} (\mod{\frac{56}{8}}) 4x \equiv 5 (\mod{7}) 4^{-1} \equiv 2 (\mod{7}) 2 \cdot 4 \cdot x \equiv 2 \cdot 5 (\mod{7}) x \equiv 10 (\mod{7})
Případně také stránky 17, 18. Tady jsem se z Bezoutem nechtěl trápit, protože na tu inverzi "kouknu a vidím".
Všiml jsem si. Ale chtěl jsem to napsat tak, jak to je v přednáškách, aby to bylo snadněji pochopitelné a aby si to mohl každý snadno dohledat (wild-guess by mohl být problematický, kdyby pro řešení bylo potřeba splnit nějaké další podmínky).
Josef Kokeš (Nov 23 '14)answered Nov 23 '14
Jako minimalne wild-guess muze byt si zkratit rovnici co to jde takze 4x = 5 mod 7 a pak muzes upravit tak ze udelas 4x*4^-1 = 5 *4^-1 mod 7 a to je x = 5 * 2 mod 7 a to je zas x = 10 mod 7 . Ale myslim ze mne matematikari ukamenujou
jinak uplne korektni postup je asi najit bezutovy koeficienty z toho zjistit x1 coz je nejake reseni a pak z neho najdes vsechny reseni jako x = x1 mod (m/gcd(a,m))
Asked: Nov 23 '14
Seen: 377 times
Last updated: Nov 23 '14
Copyright students of FIT CTU and others, 2014. Content on this site is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.