Równanie diofantyczne

destiny110 · Post autor: **destiny110** » 13 sty 2016, o 22:42

Mam problem z rozwiązaniem zadania \(\displaystyle{ 3 x+5 y=149}\) . Jak obliczyć tutaj algorytm Euklidesa, skoro dla \(\displaystyle{ NWD(3,5)}\) nie ma wspólnych dzielników?

Premislav · Post autor: **Premislav** » 13 sty 2016, o 22:55

Jeśli chcesz koniecznie skorzystać z algorytmu Euklidesa, to można trochę ten syf przekształcić:
np. tak \(\displaystyle{ 3(x-16)+5(x-20)=1}\) (odjąłem stronami \(\displaystyle{ 148}\) i rozpisałem jakoś na oko), a następnie wykonujesz rozszerzony algorytm Euklidesa dla trójki i piątki, z \(\displaystyle{ x'=x-16}\) oraz \(\displaystyle{ y'=y-20}\). Wyliczysz odpowiednie \(\displaystyle{ x'}\) i \(\displaystyle{ y'}\), a dalej z tej zależności także \(\displaystyle{ x}\) i \(\displaystyle{ y}\).

Pinionrzek · Post autor: **Pinionrzek** » 13 sty 2016, o 23:04

Można też po prostu rozwiązać najpierw zwyczajnie równanie \(\displaystyle{ 3x+5y=NWD(5, 3)=1}\), a potem zastosować wzór rekurencyjny na kolejne rozwiązania.

destiny110 · Post autor: **destiny110** » 13 sty 2016, o 23:07

Czy to będzie coś takiego
\(\displaystyle{ 5=3 \cdot 1+2}\)
\(\displaystyle{ 3=2 \cdot 1+1}\)
\(\displaystyle{ 2=2 \cdot 1}\)

\(\displaystyle{ 1=3-2 \cdot 1=3-(5-3 \cdot 1)=(-1) \cdot 5+3 \cdot 2}\) ?-- 14 sty 2016, o 00:13 --Czyli
\(\displaystyle{ x=-1+5t}\)
\(\displaystyle{ y=2-3t}\) ? Czy to jest dobrze? Ale nie wiem co dalej z tym...

Pinionrzek · Post autor: **Pinionrzek** » 13 sty 2016, o 23:26

No rozwiązanie tego wyjściowego równania będzie się wyrażało przez \(\displaystyle{ (x, y)=(-149+5t, 298+3t)}\) dla dowolnego \(\displaystyle{ t}\) całkowitego.

destiny110 · Post autor: **destiny110** » 13 sty 2016, o 23:59

A mogę widzieć dlaczego tak? -- 14 sty 2016, o 01:07 --A już wiem Dziękuję bardzo