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
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Hint: $\gcd(a,b)$ divides both $a$ and $b$, so if you divide both sides of the equation by $\gcd(a,b)$ ...
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.
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
We can prove a general result just using the basic facts: $d|k$, $d|k'$ implies $d|km$ and $d|k+k'$.
Theorem For all $a,b,x,y,m \in \mathbb Z$, $ax+by=m$ implies $(a,b)|m$ and $(x,y)|m$.
proof $(a,b)|a$ and $(a,b)|b$ so $(a,b)|ax$ and $(a,b)|by$ so $(a,b)|ax+by$, symmetry gives us $(x,y)|m$.
Corollary If $ux+vy=1$ then $(x,y)=1$
Given $ax+by=(a,b)$ put $a=(a,b)u$, $b=(a,b)v$ and divide by $(a,b)$ to get $ux+vy=1$.