Równanie diofantyczne z algorytmem Euklidesa

[BigPaws]

Rozwiązując pewne zadanie utknąłem na niżej przedstawionym etapie.

\(\displaystyle{ 19 x + 23 y = 3}\)

Liczę \(\displaystyle{ NWD(23, 19)}\):

\(\displaystyle{ 23=19 \cdot 1+4\\
19=4 \cdot 4+3\\
4=3 \cdot 1+1\\
3=3+1=0}\)

Wiem teraz, że powinienem zastosować odwrotny algorytm Euklidesa i może tu gdzieś popełniam błąd:

\(\displaystyle{ 1=4+3(-1)\\
1=4+(19+4 \cdot 4) \cdot (-1)\\
1=4-19+4 \cdot 4= -19 +4 \cdot 5\\
-19 +(23+19 \cdot (-1)) \cdot 5\\
-19+23 \cdot 5 + 19 \cdot (-5)\\
23 \cdot 5 + 19(-6)}\)

Zatem zakładam teraz, że
\(\displaystyle{ x_0=5 \\
y_0=(-6)}\)

Nie mam pojęcia co dalej. Prosze o pomoc.

[Premislav]

Same obliczenia są poprawne.

Skoro \(\displaystyle{ 5\cdot 23+(-6)\cdot 19=1}\), to

\(\displaystyle{ 15 \cdot 23+(-18)\cdot 19=3}\)
- po prostu pomnożyłem stronami przez trzy. A więc:
dla dowolnego \(\displaystyle{ t \in \ZZ}\) jest także
\(\displaystyle{ (15+19 t)\cdot 23+(-18-23 t)\cdot 19=3}\),
więc pary postaci
\(\displaystyle{ (x,y)=(15+19t, -18-23t)}\) dla \(\displaystyle{ t \in \ZZ}\) są rozwiązaniami.

[BigPaws]

Innymi słowy (bo chcę wiedzieć, czy dobrze zrozumiałem co tutaj widzę), mnożę \(\displaystyle{ x_0, y_0}\) przez prawą stronę równania bez niewiadomych.

Następnie do mojego wymnożonego już \(\displaystyle{ x_0}\) dodaję liczbę stojącą przy x a do wymnożonego \(\displaystyle{ y_0}\) liczbę przeciwną? do stojąca przy y i mnożę je przez t.

Pewnie zagmatwałem, jest jakiś wzór na który mógłbym spojrzeć żeby nie mieć wątpliwości już przy innych zadaniach? I dziękuję za sprawdzenie.

[Premislav]

No mniej więcej jest tak, jak piszesz. Ogólnie jeżeli para \(\displaystyle{ (x_0,y_0)}\) stanowi rozwiązanie równania diofantycznego \(\displaystyle{ ax+by=c}\), gdzie \(\displaystyle{ \NWD(a,b)=1}\) i \(\displaystyle{ c\nmid a, c\nmid b}\) (można takie rozwiązanie szczególne znaleźć właśnie za pomocą rozszerzonego algorytmu Euklidesa dla \(\displaystyle{ a,b}\), a potem po prostu pomnożyć przez \(\displaystyle{ c}\))
jest seria: \(\displaystyle{ (x_0+bt, y_0-at)}\) dla dowolnych \(\displaystyle{ t \in \ZZ}\)