Finding integers $x$ and $y$ such that $633x + 255y = 6$

Question

The first bit of the question asks to find the gcd of $633$ and $255$ which I did and found that it's $3$.

However, the next bit asks this:

Find integers $x$ and $y$ such that $633x + 255y = 6$, or explain why none exist.

At first I thought that the integers do exist because $3$ divides $6$ but I'm not sure if this is the right approach to this question.

Would be great if anyone could clear this up for me, thanks.

Answer 1

To do this problem, we use the extended Euclidean algorithm. The basic idea here is that we want to keep the numbers becoming smaller and smaller. For example, how many times can we subtract $633$ by $255$? The answer is $2$, so we get: $$633\cdot 1+255\cdot -2=123$$ Now, how many times can we subtract $255$ by $123$? Twice, so we get: $$(255\cdot 1)-2\cdot (633\cdot 1+255\cdot -2)=633\cdot -2+255\cdot 5=9$$ Now, how many times can we subtract $123$ by $9$? $13$ times, so we get: $$(633\cdot 1+255\cdot -2)-13\cdot(633\cdot -2+255\cdot 5)=633\cdot 27+255\cdot -67=6$$

Thus, the answer is $x=27$ and $y=-67$.

Answer 2

When $gcd$ of $633$ and $255$ is $3$, so we know that there is two numbers $a$ and $b$ such that $a\times 633 +b\times 255=3$. Now, you just need to consider $2a$ and $2b$ as your solution.