Prove that if a, b, x, y are integers with ax + by = gcd(a, b) then gcd(x,y)= 1 [closed]

How would I go about proving this: Prove that if a, b, x, y are integers with ax + by = gcd(a, b) then gcd(x,y)= 1

Solution 1:

Hint $\rm\ ax\!+\!by = c\:|\:a,b,\ d|\:x,y\:\Rightarrow\: cd\:|\:ax\!+\!by=c\:\Rightarrow\: d\:|\:1.\ \ $ Let $\rm\:c = (a,b),\ d = (x,y)\ \ $ QED

Solution 2:

Hint: $\gcd(a,b)$ divides both $a$ and $b$, so if you divide both sides of the equation by $\gcd(a,b)$ ...

Solution 3:

HINT: Show that $\gcd(a,b)\cdot\gcd(x,y)$ divides $ax+by$ and therefore divides $\gcd(a,b)$.

Added: Let $d=\gcd(a,b)$; by definition there are integers $a'$ and $b\,'$ such that $a=a'd$ and $b=b\,'d$, so $a'dx+b\,'dy=d$. (At this point I’ll depart from my hint to follow an even easier path.) Dividing through by $d$, we see that $a'x+b\,'y=1$.

Now let $e=\gcd(x,y)$. As before, there are integers $x'$ and $y\,'$ such that $x=ex'$ and $y=ey\,'$. Substituting these into the previous equation, we get $a'ex'+'ey\,'=1$, or $e(a'x'+b\,'y\,')=1$. Since $a'x'+b\,'y\,'$ is an integer, this implies that $e=1$ or $e=-1$: these are the only divisors of $1$. But $e$ is a greatest common divisor and hence by definition positive, so $e=1$.

Most of this is just using basic definitions. What does it mean to say that $d$ is $\gcd(a,b)$? It means very specifically that there are integers $a'$ and $b\,'$ such that $a=a'd$ and $b=b\,'d$, so we try to make use of this, and we get the equation $a'x+b\,'y=1$. With a little experience you can look at that and say immediately that $x$ and $y$ cannot have a common factor greater than $1$, because then the lefthand side would be divisible by that factor, and therefore $1$ would be as well $-$ which is clearly impossible. With less experience you simply investigate, as I did in the proof above, what $\gcd(x,y)$ can be.