Równanie diofantyczne

[blackbird936]

Spośród wszystkich rozwiązań równania diofantycznego \(\displaystyle{ 477x + 479y = 2259}\) wskaż to, w którym\(\displaystyle{ x}\) jest najmniejszą dodatnią liczbą całkowitą.


Czy to:
\(\displaystyle{ x=68}\)
\(\displaystyle{ y=-63}\)

?

[Koryfeusz]

Tak!

\(\displaystyle{ \NWD(477.479)=1 \wedge 1 | 2259 \Rightarrow \NWD(477,479)=477 \cdot X + 479 \cdot Y = 1 \\

1 = 477 - 2 \cdot 238 = 477 - (479 - 477 \cdot 1)\cdot 238 = 239 \cdot 477 + (-238) \cdot 479 \\
1 \cdot 2259 = [239 \cdot 477 + (-238) \cdot 479] \cdot 2259 \\
2259 = 539901 \cdot 477 + (-537642) \cdot 479 \Rightarrow X_{o}= 539901 \wedge Y_{o}=-537642 \\}\)

Rozwiązanie ogólne takiego równania diofantycznego ma postać:

\(\displaystyle{ \begin{cases}
X=X_{o}+479 \cdot t = 539901 +479 \cdot t\\
Y=Y_{o} - 477 \cdot t = -537642 - 477 \cdot t \\
t \in \mathbb{Z}
\end{cases}}\)

Pierwsze nieujemne X dostaniemy dla \(\displaystyle{ t=-1127}\) i wtedy otrzymamy rozwiązanie:

\(\displaystyle{ \begin{cases}
X=539901+479 \cdot (-1127) = 68 \\
Y=-537642 - 477 \cdot (-1127) = -63
\end{cases}}\)