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.
GCD and relative primes
-
0@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$. – 2011-09-30
3 Answers
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\:.$