Wyznacz liczby całkowite

[max123321]

Wyznacz za pomocą rozszerzonego algorytmu Euklidesa liczby całkowite \(\displaystyle{ x}\) i \(\displaystyle{ y}\) spełniające zależność:

\(\displaystyle{ 27x+4y=5}\)

[Premislav]

\(\displaystyle{ x=3, y=-19}\) pasuje. Zatem odpowiedź to \(\displaystyle{ x=3-4k, y=-19+27k, k \in \ZZ}\). To jest tzw. rozwiązanie zgadnięte, niezgodne z poleceniem, ale za szybko się pisało.

A pełne rozwiązanie:
można to zapisać w postaci
\(\displaystyle{ 27x+4(y-1)=1}\)
I teraz szukamy takich \(\displaystyle{ x, z \in \ZZ}\) (gdzie \(\displaystyle{ z=y-1}\)), że
\(\displaystyle{ 27x+4z=1}\). No to korzystamy z algorytmu Euklidesa:
\(\displaystyle{ 27=6\cdot 4+3\\4=1\cdot 3+1}\)
Zatem \(\displaystyle{ 1=4-3\cdot 1=4-(27-6\cdot 4)=7\cdot 4-27}\)
Czyli widzimy, że \(\displaystyle{ x=-1, z=7}\) spełniają to równanie
\(\displaystyle{ 27x+4z=1}\) i zauważmy, że wobec tego każda para
\(\displaystyle{ (x,z)=(-1+4k, 7-27k)}\) dla \(\displaystyle{ k \in \ZZ}\) spełnia to równanie.
Skoro \(\displaystyle{ z=y-1}\), to \(\displaystyle{ y=z+1}\) i rozwiązania wyjściowego równania są w postaci:
\(\displaystyle{ (x,y)=(-1+4k,8-27k)}\) dla \(\displaystyle{ k \in \ZZ}\)