$\gcd(a,b)\gcd(x,y)\mid ax+by$ 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.
 A: 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'|$.
A: 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.
A: Hint $\rm\ \,(a,b)\:(x,y)\ |\ a\ x + b\ y = (a,b)\ \Rightarrow\  (x,y)\ |\ 1\ \:$ by cancelling $\rm\:(a,b)\neq 0$
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. Thus $\rm\ (a,b)\ |\ a,\, \ (x,y)\ |\ x\  \Rightarrow \ (a,b)\:(x,y)\ |\ a\ x\,$ by the Divisibility Product Rule. Similarly it divides $\rm\,by,\,$ so also their sum $\,\rm ax+by$.
A: Since, $d = (a, b)$
Let $a = dk_1, b = dk_2$
$\therefore ax + by = d \\ \Rightarrow dk_1x + dk_2y = d \\ \Rightarrow k_1x + k_2y = 1$
By Bezout's Theorem, x and y are relatively prime.
