Rozszerzony algorytm Euklidesa

[Sejuanka]

Stosując rozszerzony algorytm Euklidesa znaleźć \(\displaystyle{ x, y}\) takie, że \(\displaystyle{ 8x+27y=11}\).

\(\displaystyle{ NWD(8,27)=8a+27b}\)
\(\displaystyle{ 1=8a+27b}\)
\(\displaystyle{ a=-10 \wedge b=3}\)
\(\displaystyle{ x=11a \wedge y=11b}\)
\(\displaystyle{ 8\cdot (-110)+27\cdot 33=11}\)

Takie coś mi jedynie przyszło do głowy, ale jest to bardziej zgadywanie w momencie w którym mam wyliczyć co będzie pasowało pod 1 a zgadnąć to ja sobie moge na początku odpowiedź \(\displaystyle{ x=-2 \wedge y=1}\). Jak to zrobić 'legalnie'?

[musialmi]

Wymyśliłem takie coś:
\(\displaystyle{ 8x+27y=11=8+3 \\
8(x-1)+27y=3}\)
Wiemy, że 27 dzieli 3. To znajdźmy liczbę, której \(\displaystyle{ NWD(27,8k)=3}\). Można sobie zgadnąć banalnie, że takim \(\displaystyle{ k}\) jest \(\displaystyle{ 3}\). No i teraz korzystamy z algorytmu Euklidesa, a następnie z odwrotnego algorytmu Euklidesa i dostajemy wynik.

[Sejuanka]

Szczerze to tak nie bardzo mi się wydaje żeby o takie coś chodziło