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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Try dividing everything by $d$ – talkloud Sep 30 '11 at 0:18
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. These sort of pleasantries usually result in more and better answers. Thank you. – Arturo Magidin Sep 30 '11 at 0:19
See… – TMM Sep 30 '11 at 0:25
Sorry for the bad etiquette, I haven't explored this site enough to really understand the ins and outs. But thanks for the tip. I tried dividing everything by d to receive (ax/d) + (by/d) = 1. It is known that d|a and d|b, so it can be seen that d|ax and d|by. But from this I'm struggling to see how (x,y) can equal 1 – johnnymath Sep 30 '11 at 2:23
@johnnymath: Then you already have it: you have$$\left(\frac{a}{d}\right)x + \left(\frac{b}{d}\right)y = 1,$$which is an integral linear combination of $x$ and $y$. Since $(x,y)$ must divide any integral linear combination of $x$ and $y$, it divides $1$, hence equals $1$. – Arturo Magidin Sep 30 '11 at 4:53

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|cite|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|cite|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|cite|improve this answer

Your Answer


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.