Show that if $ar + bs = 1$ for some $r$ and $s$ then $a$ and $b$ are relatively prime

Question

We were given the following problem as an assignment, we proved the converse in class for prime numbers; however, we can't use the assumption that $\operatorname{gcd}(a,b) = 1$. So I am struggling to think of my first possible move.

We are given $ar + bs = 1$, the only think I can think of is let $d$ be a common divisor or $ar + bs$ and then show that the $d = 1$. However, I am not really sure how to do that. If anyone could just give me a hint or two to nudge me in the right direction I would be appreciative.

Answer 1

Hint: Suppose to the contrary that $d\gt 1$ divides both $a$ and $b$. Then $d$ divides $ar$ and $\dots$.

Answer 2

Hint $\ $ Suppose $\,d\mid a,b\,$ is a common divisor of $\,a,b.\,$ From the multiples $\,a,b\,$ of $\,d\,$ we may deduce further multiples of $\,d\,$ because the set of all multiples of $\,d\,$ enjoys a nice algebraic structure: it is closed under the operations of addition and subtraction, since $\,jd\pm kd = (j\pm k) d.\,$. Further, it is closed under multiples $\,m(kd) = (mk)d.\,$ Composing these two operations we deduce that the multiples of $\,d\,$ are closed under arbitrary integer linear combinations, i.e. if $\,a,b\,$ are multiples of $\,d\,$ then so too is $\,ja+kb,\,$ for any integers $\,j,k.$ In your case you happen to know a very small such linear combination which, being a multiple of $\,d,\,$ greatly constrains the possible values of $d.$

Remark $\ $ This algebraic structure of (common) multiples plays a fundamental role in algebra - something that will become much clearer when one learns about ideals and modules.