Prove: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$ I've a problem proving the following: 
If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$
I've tried to set $a = c\cdot p$ and $b = d\cdot q$. But then I'm stuck proofing it formally. 
 A: By Bézout's theorem we have:
$$\gcd(a,b)=1\iff \exists u,v\in\mathbb Z\;|\; au+bv=1$$
and writing $a=cp$ and $b=dq$ we find
$$c(pu)+d(qv)=1\iff \gcd(c,d)=1$$
A: If $c\mid a$, $d\mid b$ and $\gcd(a,b)=1$, use the implications
$$\gcd(a,b)\mathbb Z=\mathbb Z\implies\mathbb Z=a\mathbb Z+b\mathbb Z\subseteq c\mathbb Z+d\mathbb Z=\gcd(c,d)\mathbb Z\implies\gcd(c,d)\mathbb Z=\mathbb Z $$
In full generality,
$$
c\mid a,d\mid b\implies a\mathbb Z\subseteq c\mathbb Z,b\mathbb Z\subseteq d\mathbb Z\implies a\mathbb Z+b\mathbb Z\subseteq c\mathbb Z+d\mathbb Z\iff\gcd(a,b)\mathbb Z\subseteq\gcd(c,d)\mathbb Z$$
hence
$$
c\mid a,d\mid b\implies\gcd(c,d)\mid\gcd(a,b)$$
A: Hint $\  \begin{eqnarray} &&(c,d)\mid c\color{#c00}{\mid}\color{#c00}a \\ 
\rm &&(c,d)\mid d\color{#c00}{\mid}\color{#c00}b
\end{eqnarray}\ \color{}\,\Rightarrow\ (c,d)\color{#c00}{\mid}\color{#c00}{(a,b)}=1\ \ \ $ QED
where we used the universal property of the gcd $\,\ k\mid m,n \iff k\mid (m,n).$
A: Let $gcd(c,d)=e>1$
Then $e$ has a prime divisor $p$.Then $p \mid e$.We know that $e \mid c \text{ and } e \mid d \Rightarrow p \mid c \text{ and } p \mid d$.
$$p \mid d \text{ and } d \mid b \Rightarrow p \mid b$$
$$p \mid c \text{ and }c \mid a \Rightarrow p \mid a$$
So, $p$ is a common divisor of $a$ and $b$,so $p \mid gcd(a,b) \Rightarrow p|1$,that is a contradiction!
So, $gcd(c,d)=1$
