Równanie na NWD z algorytmem Euklidesa

[hgv]

Mam do zrobienia takie zadanie:
Wyznacz całkowite liczby p i q spełniające równanie

\(\displaystyle{ 6 = 542p + 296q}\)

Wydaje mi się, że trzeba skorzystać z rozszerzonego algorytmu Euklidesa, ale po rozpisaniu nie wiem co zrobić.

[robertm19]

jest porządny przykład. Jeżeli \(\displaystyle{ 6}\) jest \(\displaystyle{ NWD(542,296)}\) to zrób analogicznie.

[hgv]

Po rozpisaniu algorytmem Euklidesa wychodzą takie reszty:
\(\displaystyle{ 246, 50, 46, 4, 2}\)
Nie ma tu liczby \(\displaystyle{ 6}\) i właśnie w tym jest problem. Uwagę zwraca to, że dwie ostatnie cyfry to \(\displaystyle{ 2}\) i \(\displaystyle{ 4}\), a ich suma to \(\displaystyle{ 6}\), ale można to jakoś ze sobą powiązać?

[robertm19]

Ale to znaczy, że da się znaleźć takie \(\displaystyle{ p}\) i \(\displaystyle{ q}\) , że \(\displaystyle{ 2=542q+296p}\). A wtedy pomnożenie obu stron przez 3 ta wynik \(\displaystyle{ 6=3q542+3p296}\).

[hgv]

Ja się za chwilę załamię... Siedzę na tym od paru godzin, łączę ze sobą kolejne liczby, a wystarczy pomnożyć przez \(\displaystyle{ 3}\). Dzięki za pomoc!