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.

Suppose $a$ and $b$ are positive integers, and that $d=\gcd(a,b)$. Suppose we have found integers $x$ and $y$ such that $ax+by=d$. Prove that $x$ and $y$ are relatively prime.

share|improve this question
3  
Try dividing everything by $d$ –  J.D. Mohr Sep 30 '11 at 0:18
6  
Welcome to MathSE. I see that this is your first question. So I wanted to let you know a few things about MathSE. Posting questions in the imperative (i.e. Compute all such, Prove that...), is considered rude by some of the members, so it would be nice of you to change that wording; perhaps by adding what are your thoughts or what you have tried in trying to answer the problem. If this is homework, please add the [homework] tag; don't worry, it won't stop people form answering. These sort of pleasantries usually result in more and better answers. Thank you. –  Arturo Magidin Sep 30 '11 at 0:19
2  
See math.stackexchange.com/questions/61990/… –  TMM Sep 30 '11 at 0:25
3  
@Arturo Kudos$^\infty$ on the very nicely phrased meta-comment. –  Bill Dubuque Sep 30 '11 at 0:34
2  
@BillDubuque: Those should go to the person I "borrowed" it from: mixedmath's comment here. –  Arturo Magidin Sep 30 '11 at 2:07

3 Answers 3

If $k|x,y$, then $k|ax+by=d$, so we can write $d = kd' = ax'k + by'k$; hence $d'=ax'+by'$. Since $\gcd(a,b)|ax'+by' = d'$, then $d|d'$. Since $d'|d$, then $|d|=|d'|$.

share|improve this answer

Although you don't have to use proof by contradiction, it would be my first try.

Assume that $x$ and $y$ are not relatively prime. What does that mean? It means they have a common divisor larger than 1. So give that divisor a name, do some algebra, and see if you can reach a contradiction.

Post in the comments if you have problems.

share|improve this answer

HINT $\rm\quad (a,b)\:(x,y)\ |\ a\ x + b\ y\ =\ (a,b)\ \ \Rightarrow\ \ (x,y)\ |\ 1\ \:$ by cancelling $\rm\:(a,b)\:$

Note: $\: $ above $\rm\ (m,n)\ $ denotes $\rm\ \gcd(m,n)\:,\ $ and $\rm\ m\ |\ n\ $ means $\rm\ m\:$ divides $\rm\:n\:.\:$ This is standard number theory notation. Hence, e.g. $\rm\ (a,b)\ |\ a,\ \ (x,y)\ |\ x\ \ \Rightarrow\ \ (a,b)\:(x,y)\ |\ a\ x\:.$

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.