1
$\begingroup$

I have this math question that I am stuck on. This is the question:

Suppose that $a$ and $b$ are positive integers, with $d = \gcd(a, b)$. Suppose that there exists integers $r$ and $s$ so that $ar + bs= d$. Show that $\gcd(r, s) = 1$ using the relatively prime equation.

This is the relatively prime relationship equation: Let $a,b$ be non-zero integers. $a$ and $b$ are relatively prime iff there exists integers $x$ and $y$ such that $ax+by=1$

I know that the relatively prime equation that I have to solve is $ar + bs = 1$. However, I'm not sure how to start this. Thanks.

$\endgroup$
4
  • $\begingroup$ What is this "relatively prime equation"? As stated, you can't use Bezout's identity because that's what you are trying to prove. $\endgroup$
    – A.P.
    Oct 8, 2015 at 19:24
  • $\begingroup$ @A.P. Let $a,b$ be non-zero integers. $a$ and $b$ are relatively prime iff there exists integers $x$ and $y$ such that $ax+by=1$ $\endgroup$
    – KFC
    Oct 8, 2015 at 19:26
  • $\begingroup$ That's a special case of what you are trying to prove. $\endgroup$
    – A.P.
    Oct 8, 2015 at 19:27
  • $\begingroup$ So, how do I show it using that equation? I don't start off with the equation? $\endgroup$
    – KFC
    Oct 8, 2015 at 19:29

2 Answers 2

3
$\begingroup$

Dividing $a$ and $b$ by $d$, we have two relatively prime numbers. By the relatively prime numbers equation, it exist $r$ and $s$ such that

$r\frac{a}{d} + s\frac{b}{d} = 1.$

Those numbers are relatively prime. If not, the left part could be factorise giving an integer factorisation of 1...

Multiplying everything by $d$ again to obtain what you need

$\endgroup$
4
  • $\begingroup$ How is that using the Relatively Prime Relationship Equation? $\endgroup$
    – KFC
    Oct 8, 2015 at 19:25
  • $\begingroup$ Since $\frac{a}{d}$ and $\frac{b}{d}$, there is $r$ and $s$ such that $r\frac{a}{d} = s\frac{b}{d}=1$. $r$ and $s$ are relatively prime. $\endgroup$ Oct 8, 2015 at 19:30
  • $\begingroup$ +1: The idea's there, but you should try to flesh-out your answers a bit more. Right now this is more a comment than an answer... $\endgroup$
    – A.P.
    Oct 8, 2015 at 19:34
  • $\begingroup$ My goal was to give you a hint, I will flesh out my solution. $\endgroup$ Oct 8, 2015 at 19:35
3
$\begingroup$

We know that $a = d\bar{a}$ and $b = d\bar{b}$, so dividing $$ ar + bs = d $$ by $d$ we get $$ \bar{a}r + \bar{b}s = 1 $$ which is what you call the "relatively prime equation", hence $r$ and $s$ must be coprime.

To conclude without assuming this, just suppose that there is an $f > 1$ that divides both $r$ and $s$. Then the above equation implies $f \mid 1$, which is absurd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.