Ask Your Question
2

Podmínky na řešení kongruence

asked 2014-11-23 12:50:22 +0100

Iva Houdková gravatar image

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ší.

edit retag flag offensive close delete

2 Answers

Sort by » oldest newest most voted
1

answered 2014-11-23 13:28:23 +0100

Josef Kokeš gravatar image

updated 2014-11-23 13:45:58 +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".

edit flag offensive delete publish link more

Comments

to jsem tak nejak napsal, ale ve vic divoke forme :D

Jakub Průša ( 2014-11-23 13:46:37 +0100 )edit

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 )edit
1

answered 2014-11-23 13:24:02 +0100

Jakub Průša gravatar image

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))

edit flag offensive delete publish link more

Comments

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 )edit

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2014-11-23 12:50:22 +0100

Seen: 377 times

Last updated: Nov 23 '14