2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: $amx + bry = (mx)a + (ry)b = 1$. $\endgroup$ – Dilip Sarwate Oct 22 '14 at 2:35
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.