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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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\:.$