Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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

share|improve this answer
    
So since ax+by=gcd(a,b) if I divide by the gcd(a,b) the equation that I am left with is equal to 1. Would this prove that gcd(x,y) must be 1? –  Anthony Nov 5 '12 at 22:30
    
I think you got it from Brian Scott's helpful response. But yes, if you know that $a' x + b' y = 1$, then $\gcd(x,y)=1$ because you hopefully proved a theorem in your class that $\gcd(x,y)$ is the smallest positive integer that can be written in the form $rx + sy$ with $r,s \in \mathbb{Z}$. So if you can write $1$ in this form, it must be the $\gcd$. –  Michael Joyce Nov 5 '12 at 23:16

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.

share|improve this answer
    
How would I show this? I'm even worse at proofs than I am at Congruence. Would that simply be enough? Or would I need more detail –  Anthony Nov 5 '12 at 22:26
    
@Anthony: Let me write this one up in detail to give you an idea of the kinds of argument that you can expect to be asked to make. –  Brian M. Scott Nov 5 '12 at 22:28
    
OK thank you I appreciate it. –  Anthony Nov 5 '12 at 22:33
    
Thank you very much my proofs are quite weak and this was very helpful. –  Anthony Nov 5 '12 at 22:46
    
@Anthony: My pleasure; I’m glad that it helped. –  Brian M. Scott Nov 5 '12 at 22:50

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

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.