Prove divisibility with gcd: If $ar+bs=d=\gcd(a,b)$, then $r$ and $s$ are relatively prime 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
 A: 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$.
A: 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$.
A: 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$.
A: 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.$
