# GCD and relative primes

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.

-
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. 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
– TMM Sep 30 '11 at 0:25
@Arturo Kudos$^\infty$ on the very nicely phrased meta-comment. – Bill Dubuque Sep 30 '11 at 0:34
@BillDubuque: Those should go to the person I "borrowed" it from: mixedmath's comment here. – Arturo Magidin Sep 30 '11 at 2:07

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

-

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.

-

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

-