asked 2014-11-23 12:50:22 +0100
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 2014-11-23 13:28:23 +0100
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š ( 2014-11-23 13:48:22 +0100 )editanswered 2014-11-23 13:24:02 +0100
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))
A ta podmínka řešení je, že gcd(a,m) dělí b beze zbytku.
Miro Hrončok ( 2014-11-23 13:25:00 +0100 )editAsked: 2014-11-23 12:50:22 +0100
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.