Prove if $a|c$ and $b|d$ and $\gcd(c,d)=1$ then $\gcd(a,b)=1$

Question

I'm trying to prove that if $a|c$ and $b|d$ and $\gcd(c,d)=1$ then $\gcd(a,b)=1$

So far, I have assumed that:

Since $\gcd(c,d) = 1$ then by EEA, $$\gcd(c,d) = 1 = cx + dy$$ for some $x,y$ that are integers. And since $a|c$ and $b|d$ then $c=am$ and $d=br$ for some $m,r$ that are integers.

I just don't know where to go from here. Thanks you.

Answer 1

You're really close to the answer! As of now, you have the three equations (for integer $x,y,m,r$) $$1=cx+dy$$ $$c=am$$ $$d=br$$ The only thing you need do from there is to substitute the last two equations into the first one - that is, get $$1=(am)x+(br)y$$ $$1=a(mx)+b(ry)$$ and, hey presto, we have a sum of $a$ and $b$ with integer coefficients $mx$ and $ry$ equaling $1$, so they must be coprime.

Answer 2

Hint: $gcd(a,b)|a$, $gcd(a,b)|b$, hence $gcd(a,b)$ divides both $c$ and $d$...

Answer 3

Hint. Let $g$ be a (positive) common factor of $a$ and $b$. Our aim is to show that $g$ has to be $1$, no other possibility.

In view of the information given, can you see how $g$ is related to $a$? Can you see how it is related to $b$? Can you then solve the problem?