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.

| cite | improve this question | |
$\endgroup$
  • $\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 '15 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 '15 at 19:26
  • $\begingroup$ That's a special case of what you are trying to prove. $\endgroup$ – A.P. Oct 8 '15 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 '15 at 19:29
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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How is that using the Relatively Prime Relationship Equation? $\endgroup$ – KFC Oct 8 '15 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$ – Alain Remillard Oct 8 '15 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 '15 at 19:34
  • $\begingroup$ My goal was to give you a hint, I will flesh out my solution. $\endgroup$ – Alain Remillard Oct 8 '15 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.

| cite | improve this answer | |
$\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.