Matematické Fórum

dmoor · 08. 11. 2015 21:53 — Editoval dmoor (08. 11. 2015 21:57)

Dobrý den,

mám rovnici m1*353+m2*277-968782039753030=0 řešeno v N0.

Existuje nějaký vzorec jak se dostat k počtu možných řešení?

Díky.

check_drummer · 08. 11. 2015 22:32

↑ dmoor:
Ahoj, nejdřív nalézt tvar řešení v Z (pokud vůbec nějaká existují) - na t oex. teorie - a pak zkoumat, kdy jsou obě kladná.

Eratosthenes · 09. 11. 2015 09:45

ahoj ↑ check_drummer:,

Tvůj návod mi připomíná Old Shaterhanda, který počítal mustangy v pádícím stádu: spočítal nohy, a pak to dělil čtyřmi :-)

Eratosthenes · 09. 11. 2015 10:12

ahoj ↑ dmoor:,

"vzorec" existuje. Jmenuje se hrubá síla počítače. Tu necháme najít první řešení. Ta další už jsou snadná.

V našem případě je

m1 = 2 744 425 041 572
m2 = 282

Všechna řešení jsou tvaru m1 - k*277 + m2 +k*353; k=0;1;....;2 744 425 041 792

Čili těch řešení je 2 744 425 041 793.

teemo · 09. 11. 2015 10:29 — Editoval teemo (09. 11. 2015 14:53)

↑ Eratosthenes: mohol by si trošku ozrejmiť ako nájsť to prvé riešenie? alebo ako si sa dopracoval k m1 - k*277 + m2 +k*353. Vďaka

Eratosthenes

ahoj ↑ teemo:,

no, nejsem sice žádný odborník na diofantické rovnice, ale zkusím to. Vezměme to s jednoduchými čísly - mám nalézt přirozená řešení rovnice

$5\cdot m_1+3\cdot m_2-59=0$

Pro reálné $m_1; m_2$ je to rovnice přímky, kterou si vyjádřím ve směrnicovém tvaru, a to tak, aby $|k|<1$ . V tomto případě tedy

$m_1=-\frac 3 5\cdot m_2+\frac {59} 5$

Vezmu postupně $m_2=0;1;2;...$ . Tím dostávám lineární rovnice s jedinou neznámou $m_1$ , kterou vždy dopočítám. Až vyjde přirozené číslo, mám "první řešení". Vtip je v tom, že všechna čísla v poslední rovnici jsou racionální, takže dříve či později musí vyjít m_1 celočíselné, ale může vyjít záporné. V tom případě přirozené řešení není. Hledám-li přirozené řešení, stačí (v tomto případě) hledat pro $m_2<\frac{59} 3$ . Nenajdu-li ho, přirozené řešení není.

Tuto otročinu pro větší čísla lze přenechat počítači. Mohli bychom ho nechat prohledat všechny možnosti, v modelovém příkladě tedy $m_1=0;1;...;19$ , ale je to zbytečné. V zadaném příkladu by to trvalo možná i několik hodin, kdežto první řešení bylo prakticky okamžitě. Ta další řešení snad budou zřejmá z následujícího obrázku:

//forum.matweb.cz/upload3/img/2015-11/82441_Diofant.png

Červenými body prokousává počítač až k $m_2=3$ najde $m_1=10$ . Další řešení už "zařídí" ta racionální směrnice.

check_drummer · 09. 11. 2015 19:20

↑ Eratosthenes:
Je chybou domnívat se, že pokud zkoumám daný problém ve "větším" prostoru, že je to obtížnější...

Eratosthenes · 09. 11. 2015 21:27

↑ check_drummer:

"Větší" prostor samozřejmě vždycky obtížnější být nemusí. Tady si myslím, že je to nejen obtížnější, ale i zbytečné.

check_drummer · 09. 11. 2015 21:30

Eratosthenes napsal(a):
V našem případě je

m1 = 2 744 425 041 572
m2 = 282

Všechna řešení jsou tvaru m1 - k*277 + m2 +k*353; k=0;1;....;2 744 425 041 792

Ahoj, není zřejmé co je myšleno tím "m1 - k*277 + m2 +k*353" - řešení je přece dvojice a nikoli jediný výraz...

Eratosthenes

ahoj ↑ check_drummer:

Ano, omlouvám se, napsal jsem to špatně. Bylo tím myšleno

[m1;m2]+k*[-277;353]; k=0;1;....;2 744 425 041 792

Matematické Fórum

#1 08. 11. 2015 21:53 — Editoval dmoor (08. 11. 2015 21:57)

Počet možných řešení

#2 08. 11. 2015 22:32

Re: Počet možných řešení

#3 09. 11. 2015 09:45

Re: Počet možných řešení

#4 09. 11. 2015 10:12

Re: Počet možných řešení

#5 09. 11. 2015 10:29 — Editoval teemo (09. 11. 2015 14:53)

Re: Počet možných řešení

#6 09. 11. 2015 16:25 — Editoval Eratosthenes (09. 11. 2015 16:28)

Re: Počet možných řešení

#7 09. 11. 2015 19:20

Re: Počet možných řešení

#8 09. 11. 2015 21:27

Re: Počet možných řešení

#9 09. 11. 2015 21:30

Re: Počet možných řešení

Eratosthenes napsal(a):

#10 09. 11. 2015 21:38 — Editoval Eratosthenes (09. 11. 2015 21:38)

Re: Počet možných řešení

Zápatí