Prove divisibility with gcd: If $ar+bs=d=\gcd(a,b)$, then $r$ and $s$ are relatively prime

Question

I have this math problem. The question is:

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$. We want to show that $r$ and $s$ are relatively prime using the following procedures:

i) Let $k \in \mathbb{Z}$ such that $k \mid r$ and $k \mid s$. Use "If $A\mid C$ and $B\mid D$, then $AB\mid CD$" to show that $kd \mid d$.

ii) Use the result from part i to conclude that $ k \le 1$ and hence $\gcd(r, s) = 1$. This prove that $r$ and $s$ are relatively prime.

So far I have that we know that since $k\mid r$ then $k\mid ar$. We also know that since $k\mid s$, then $k\mid bs$. So, since $k\mid ar$ and $k\mid bs$ we know $k\mid (ar+bs)$. Therefore, $k\mid d$. However, I'm not sure where to go from here. Thanks

Answer 1

First Proof

Claim. $kd\mid d$.

Proof $d\mid a \land k\mid r \implies kd\mid ar$

$d\mid b \land k\mid s \implies kd\mid bs$

$\therefore kd\mid ar+bs\implies kd\mid d\implies ??$

Second Proof

But I think that the proof can be done in much simple way if you just notice that $r\left(\dfrac{a}{d}\right)+s\left(\dfrac{b}{d}\right)=1$. Then from Bezout's Identity you can easily conclude that $\gcd(r,s)=1$.

Answer 2

Do what they say. You have $k\mid r$ and $d\mid a$ so you have $kd\mid ar$. You have $k\mid s$ and $d\mid b$ so you have $kd\mid bs$ so you have $kd\mid ar + bs = d$. So you have $kd\mid d$.

Thus $k\leq 1$, which means $1$ is the largest number that divides both $r$ and $s$ so $\gcd(r,s) =1$.

Answer 3

By the result with caps that they quote, from $k$ divides $r$ and $d$ divides $a$ we conclude that $kd$ divides $ra$. Similarly, $kd$ divides $sb$. So $kd$ divides the sum $ra+sb$, and therefore $kd$ divides $d$. For positive $k$ this is only possible if $k=1$.

Answer 4

Use the technique of incorporating new information into a given equation: Let $a=da'$ and $b=db'$ where $a',b'$ are integers. The main equation is then $$d=ar+bs=da'r+db's=d(a'r+b's).$$

We can divide through by $d$ to get $a'r+b's=1.$ Now if $e$ is any common divisor of $r$ and $s,$ we have $$(e|r\land e|s)\implies (e|a'r\land e|b's)\implies e|(a'r+b's)=1\implies e=\pm 1.$$

Footnote: $\gcd (a,b)$ is not $0$ if $a$ and are not both $0,$ and $\gcd(0,0)$ does not exist. The hypothesis $d=ar+bs\in \Bbb Z$ implies that $d$ exists, implying $d\ne 0.$ So we $can$ divide by $d.$