Suppose there are integers $a,b,x$ and $y$ such that $ax +by = 5$, and $5$ does not divide $x$. What is $\gcd(x,y)$?
I have been trying to figure out this question for some time. However, I do not even know how to start.
I tried rewriting the equation:
$$5 = ax+by$$
Then I made everything into mod $x$,
$$5\pmod{x} \equiv ax\pmod{x} + by\pmod{x}$$
$$5\equiv by\pmod{x}$$
I couldn't figure out how to continue from here.
Can anyone help me with this? I am very stuck and I do not know how to solve this problem.
Let $d>0$ be a common divisor of $x$ and $y$ then $d$ divides $ax+by=5$. Since $5$ is prime it follows that $d=1$ or $d=5$. Now, we note the assumption "5 does not divide $x$". What may we conclude about $d$? What is $\gcd(x,y)$, i.e. the greatest common divisor of $x$ and $y$?