If $ar + bs =1$, then $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$ [duplicate]

Here's the question:

Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that

$$ar + bs =1.$$

Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$.

I was stuck how to solve this problem. My first instinct is to do a proof by contradiction, that is, assume the $\gcd(a,s) > 1$ - therefore there exists a $d > 1$ such that $a = dn$ for an integer $n$ and $s = dm$ for an integer $m$. However, I don't know where to go from here (or even if this is the correct route).

I would really appreciate some help - thank you in advance for everything!

Thanks!

Solution 1:

You actually only need to know that $ar+bs=1$, it then follows that $$\gcd(a,b)=\gcd(a,s)=\gcd(r,b)=\gcd(r,s)=1.$$

A proof is as follows: the $\gcd$ of $a,b$ divides the expression $ar+bs$, since it divides both $a$ and $b$. Therefore it divides 1, which means it must be equal to 1. You then perform similar arguments replacing the pair $(a,b)$ with $(a,s)$, $(r,b)$ or $(r,s)$.

Solution 2:

All the integers in the equation are on equal footing, we know that the gcd of two numbers divides every integral combination of the two, since only $1|1$ in natural numbers, if we pick our "special" integers to be $a,s$ then we note the corresponding integers in the Euclidean algorithm process are $r, b$ and so the first result follows. The exact same argument holds when we declare $r,b$ and $r,s$ to be special with corresponding pairing integers $a,s$ and $a,b$ respectively.

More explicitly, if you don't know that theorem on gcd dividing all the integer combinations, just let $d>0$ and $d|a, d|s$ then

$$\begin{cases} a=dk \\ s = dj\end{cases}$$

so $d(kr+jb)=1$ and $d|1\implies d=1$

Again, you clone the argument for the other choices. Successively writing $r=d\ell, b=dm$ and $r=dn, s=dp$ and each time concluding $d|1\implies d=1$.