Równanie diofantyczne

[icK]

Podać rozwiązanie ogólne liniowego równania diofantycznego

\(\displaystyle{ 207x + 253y = 3013}\)

Policzyłem że NWD = 23

[kerajs]

\(\displaystyle{ 9x+11y=131\\
x= \frac{131-11y}{9}\\
x= 14-y+ \frac{5-2y}{9}\\
y=-2+9k \Rightarrow x=14-(-2+9k) + \frac{5-2(-2+9k )}{9}= 17-11k, \ \ dla \ k \in C}\)

[0Mniac]

\(\displaystyle{ x= 14-y+ \frac{5-2y}{9}\\
y=-2+9k}\)

Mógłbyś wytłumaczyć skąd to przejście?

[kerajs]

Ale to nie jest przejście.

Tam było trochę więcej:

\(\displaystyle{ x= 14-y+ \frac{5-2y}{9}\\
y=-2+9k \Rightarrow x=14-(-2+9k) + \frac{5-2(-2+9k )}{9}= 17-11k, \ \ dla \ k \in C}\)

czyli:
\(\displaystyle{ x= 14-y+ \frac{5-2y}{9}}\)
Gdy całkowite y-grek będzie postaci \(\displaystyle{ y=-2+9k}\) to x przyjmie wartości całkowite postaci: \(\displaystyle{ x= 17-11k}\) dla każdego całkowitego k.

[0Mniac]

Dalsza część jest zrozumiała, ale niestety nie wiem skąd wziął się zapis \(\displaystyle{ y=-2+9k}\). Wiem, że równanie to ma postać \(\displaystyle{ y= y_{0} + k}\), ale nie wiem czy krotność \(\displaystyle{ k}\) jak i \(\displaystyle{ y_{0}}\) uzyskałeś w jakiś sposób odczytując z poprzednich równań czy na przykład użyłeś algorytmu euklidesa, czy jak to wygląda?

[kerajs]

Mam
\(\displaystyle{ x= 14-y+ \frac{5-2y}{9}}\)
Aby x było całkowite to ułamek musi także być liczbą całkowitą. Nie stosowałem żadnego algorytmu lecz odgadłem sobie postać y-greka. Równie dobrze mogłem napisać \(\displaystyle{ y=16-9k}\) , \(\displaystyle{ y=-11+9k}\) lub jeszcze inaczej.
Gdybym musiał ubrać to w jakiś schemat to: y musi być postaci: \(\displaystyle{ y=ak+b}\)
Wtedy:
\(\displaystyle{ \frac{5-2(ak+b)}{9}= \frac{5-2b}{9}+ \frac{-2ak}{9}}\)
Chcę aby \(\displaystyle{ \frac{5-2b}{9}}\) było całkowite więc odgaduję dowolne b skracające ułamek do liczby całkowitej (najproszte b to -2) lub męczę:
\(\displaystyle{ 5-2b=9p \Rightarrow b= \frac{5-9p}{2}}\) gdzie p jest dowolną liczbą nieparzystą. Obliczam b dla np:\(\displaystyle{ p=-1}\): \(\displaystyle{ b= \frac{5+9}{2}=7}\)
Aby \(\displaystyle{ \frac{-2ak}{9}}\) było całkowite dla dowolnego całkowitego k to a musi wynosić 9. Gdyby było jego wielokrotnością to rozwiązanie wskazywałoby tylko na część rozwiązań.
Dostałem: \(\displaystyle{ y=9k+7}\).
Teraz wyliczam x:
\(\displaystyle{ x= 14-(9k+7)+ \frac{5-2(9k+7)}{9}=14-9k-7+ \frac{5-18k-14}{9}=7-9k-1-2k=6-11k}\)
Rozwiązanie równania to para:
\(\displaystyle{ \begin{cases} x=6-11k \\ y=9k+7 \end{cases} \ \ gdzie \ \ k \in C}\)
Moje rozwiązanie dostaniesz przy podstawieniu \(\displaystyle{ k=K-1}\)
\(\displaystyle{ \begin{cases} x=6-11(K-1) \\ y=9(K-1)+7 \end{cases} \ \ gdzie \ \ K \in C}\)
\(\displaystyle{ \begin{cases} x=-11K+17 \\ y=9K-2 \end{cases} \ \ gdzie \ \ K \in C}\)

Paradoksalnym jest to, że odgadnięcie postaci \(\displaystyle{ y=-2+9k}\) zajęło mi w myślach 2 sekundy, a tłumaczenie dlaczego tak można i wklepanie tego zabrało mi 20 minut.

[0Mniac]

Teraz rozumiem i ja. Dziękuję za poświęcony czas