Given d = gcd(c,n), why there exists relatively prime integers r and s, such that c = rd and n = sd

Question

Given $d = gcd(c,n)$, why there exist relatively prime integers r and s, such that $c = rd$ and $n = sd$?

Answer 1

Since $d$ is a divisor of both $c$ and $n$, there are integers $r$ and $s$ such that $c=rd,n=sd$.

If $r$ and $s$ had a positive common factor $t$, then $td$ would be a common factor of both $c$ and $n$. However, the g.c.d. of these numbers is $d$. The only possibility is therefore $t=1$ and so $r$ and $s$ are relatively prime.

Answer 2

Suppose $r$ and $s$ are not relatively prime. Then, they share a common factor greater than $1$, let's call it $k$.

Then, $c=\frac{r}{k}(dk)$ and $n=\frac{s}{k}(dk)$. So $dk$ is a common factor of $c, n$ which is greater than $d$, a contradiction. So $r, s$ must be relatively prime.