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.

  • 3
    Try dividing everything by $d$2011-09-30
  • 6
    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. These sort of pleasantries usually result in more and better answers. Thank you.2011-09-30
  • 2
    See http://math.stackexchange.com/questions/61990/how-to-show-that-gcda-b-axby-implies-gcdx-y-12011-09-30
  • 1
    Sorry for the bad etiquette, I haven't explored this site enough to really understand the ins and outs. But thanks for the tip. I tried dividing everything by d to receive (ax/d) + (by/d) = 1. It is known that d|a and d|b, so it can be seen that d|ax and d|by. But from this I'm struggling to see how (x,y) can equal 12011-09-30
  • 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\:.$