GCD property in the order of powers proof I am stuck on this portion of the (multiplicative) order of powers proof:
$$d = gcd(a, b)$$
$$write\; a=rd, b=sd$$
$$then \; gcd(r,s) =1 $$
How is this proven?
We know:
$$d \mid a, \; d \mid b$$
for some $k$, let $k \mid r, \; k \mid s$
then
$$km = r, kn = s$$
so
$$kmd = a, knd=b$$
$$kd \mid a, kd \mid b$$
that's where I'm stuck
 A: Hint: Can you show that $d \times {\rm gcd}(r,s)$ is a common divisor of $a$ and $b$?
So if ${\rm gcd}(r,s) > 1$, can $d$ possibly be the greatest common divisor of $a$ and $b$?
A: Let  $t=\gcd (r,s)$. Let $r=r't$ and $s=s't.$
We have $a=rd=r'(td)$ and $b=sd=s'(td).$ So $td$ is a common divisor of $a$ and $b.$
Therefore $td\leq \gcd(a,b)=d.$ Since $0<td \leq d$, this implies $t\leq 1.$
But of course $t\geq 1 .$  So $t=1.$ 
A: The actual proof I needed, which I think I can now do with the above insights is:
Show that $\frac {a}{gcd(a,b)}, \frac{b}{gcd(a,b)}$ are relatively prime.  
I would do this as follows:
Let $d = gcd(a,b)$.
We know that $d \mid a$ and $d \mid b$.
Then $dk=a$ and $dl=b$ for some $k, l$;  $\;k = \frac{a}{d}, \; l=\frac{b}{d}$.
Now if $k$ and $l$ are not relatively prime, then they have a common divisor, $d'$, such that $k=k'd'$ and $l=l'd'$. 
So $dd'k'=a$ and $dd'l'=b$.  
$dd'$ is thus a common divisor of $a$ and $b$, but for $d$ to be $gcd(a, b)$, then $d'$, this common divisor of $k$ and $l$, must be 1.
If there are any flaws in this reasoning, I would be happy to hear about them.
