# Relatively Prime Relationship Equation Proof

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.

• What is this "relatively prime equation"? As stated, you can't use Bezout's identity because that's what you are trying to prove. – A.P. Oct 8 '15 at 19:24
• @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$ – KFC Oct 8 '15 at 19:26
• That's a special case of what you are trying to prove. – A.P. Oct 8 '15 at 19:27
• So, how do I show it using that equation? I don't start off with the equation? – KFC Oct 8 '15 at 19:29

## 2 Answers

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

• How is that using the Relatively Prime Relationship Equation? – KFC Oct 8 '15 at 19:25
• 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. – Alain Remillard Oct 8 '15 at 19:30
• +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... – A.P. Oct 8 '15 at 19:34
• My goal was to give you a hint, I will flesh out my solution. – Alain Remillard Oct 8 '15 at 19:35

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.