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.
Best Answer
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