1
$\begingroup$

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.

  • 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 3

2

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

0

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.

0

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