Równanie dla liczb naturalnych

[zr3456]

Równanie: \(\displaystyle{ 59 \cdot x-60 \cdot y=550}\). Czy istnieje rozwiązanie i jakie dla liczb naturalnych \(\displaystyle{ x,y}\)?

[kerajs]

\(\displaystyle{ \begin{cases} x=60k-10 \\ y=59k-19 \\ k \in \NN_{+} \end{cases}}\)

[dec1]

Biorąc równanie modulo \(\displaystyle{ 59}\) otrzymujemy

\(\displaystyle{ -y\equiv 19 \mod{59}}\)

stąd

\(\displaystyle{ y=59k-19}\)

dla pewnej liczby naturalnej \(\displaystyle{ k}\). Podstawiając to do równania otrzymujemy

\(\displaystyle{ x=60k-10}\)

Zatem rozwiązaniami są wszystkie dwójki \(\displaystyle{ (x,y)=(60k-10,59k-19)}\) dla dowolnego naturalnego \(\displaystyle{ k}\).

[zr3456]

Wielkie dzięki za rozwiązanie; mam zapytanie, czy jest gdzieś na forum pokazane przykładowe rozwiązywanie takich typów równań, bo wreszcie chcę się je nauczyć samodzielnie rozwiązywać.

[bakala12]

Jestem zdziwiony, że w tym temacie jeszcze nie padło hasło rozszerzony algorytm Euklidesa.
... _Euklidesa

Nie będę tego dowodził, bo nie ma na to czasu, ale będę z tego algorytmu korzystał. Nie jest on jakiś trudny, wystarczy zrobić 2-3 przykłady i natychmiast załapiesz o co chodzi.

Zacznijmy od początku. Weźmy równanie diofantyczne:
\(\displaystyle{ ax+by=c}\)
gdzie \(\displaystyle{ a,b,c}\) są całkowitymi współczynnikami, a \(\displaystyle{ x,y}\) niewiadomymi. Interesują nas tylko takie rozwiązania tego równania dla których obie liczby \(\displaystyle{ x,y}\) są całkowite.
Istnieje pewne kryterium, które roztrzyga kiedy takie równanie ma rozwiązanie. Oto ono:

Równanie \(\displaystyle{ ax+by=c}\) przy założeniach powyżej posiada rozwiązanie w liczbach całkowitych wtedy i tylko wtedy gdy \(\displaystyle{ NWD\left(a,b\right) | c}\)

(Gdyby zapis był niejasny, to równanie ma rozwiązanie wtedy i tylko wtedy, gdy liczba \(\displaystyle{ c}\) dzieli się przez największy wspólny dzielnik liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\).
Udowodnimy, to stwierdzenie.
1. \(\displaystyle{ \Rightarrow}\) (Jeżeli równanie posiada rozwiązanie, to \(\displaystyle{ NWD\left(a,b\right) | c}\)
Dowód:
Niech \(\displaystyle{ d=NWD\left(a,b\right)}\). Niech \(\displaystyle{ x_{0},y_{0}}\) będą liczbami całkowitymi spełniającymi to równanie (założyliśmy, że rozwiązanie istnieje). Zachodzi więc:
\(\displaystyle{ ax_{0}+by_{0}=c}\). Zauważmy, że na mocy definicji największego wspólnego dzielnika mamy:
\(\displaystyle{ d|a}\) oraz \(\displaystyle{ d|b}\).
Stąd zaś \(\displaystyle{ d|ax_{0}}\) i \(\displaystyle{ d|by_{0}}\) i w konsekwencji \(\displaystyle{ d|ax_{0}+by_{0}}\), czyli \(\displaystyle{ d|c}\), co należało pokazać.
2. \(\displaystyle{ \Leftarrow}\) (Jeżeli \(\displaystyle{ NWD\left(a,b\right)|c}\), to równanie posiada rozwiązanie)
Dowód:
Niech znowu \(\displaystyle{ d=NWD\left(a,b\right)}\). Rozważmy równanie:
\(\displaystyle{ ax+by=d}\) w liczbach całkowitych. Na mocy rozszerzonego algorytmu Euklidesa istnieją liczby \(\displaystyle{ x,y}\) spełniające to równanie. Aby się o tym przekonać, korzystamy z algorytmu Euklidesa do znalezienia \(\displaystyle{ NWD\left(a,b\right)}\). Niech liczby \(\displaystyle{ x_{0},y_{0}}\) spełniają to nowe równanie, a więc: \(\displaystyle{ ax_{0}+by_{0}=d}\).
Zdefiniujmy liczbę:
\(\displaystyle{ m=\frac{c}{d}}\)
Ponieważ z założenia wiemy, że \(\displaystyle{ d|c}\) to wnioskujemy, że liczba \(\displaystyle{ m}\) jest całkowita. Przyjmijmy teraz \(\displaystyle{ x=mx_{0}}\) oraz \(\displaystyle{ y=my_{0}}\). Oczywiście tak zdefiniowane liczby \(\displaystyle{ x,y}\) są całkowite. Ponadto:
\(\displaystyle{ ax+by=amx_{0}+bmy_{0}=m\left(ax_{0}+by_{0}\right)=md = c}\)
Zatem, \(\displaystyle{ x,y}\) są rozwiązaniem wyjściowego równania, co kończy dowód twierdzenia.

Rozszerzony algorytm Euklidesa, daje nam więc wszystko aby takie równania rozwiązywać.

[zr3456]

Dzięki ! O to mi chodziło.