If $\gcd(a,c)=1$, then $\gcd(ab, cd) = \gcd(b, d)$?

58 Views Asked by At

I am trying to see whether that sentence holds.
I did this :
Let $\gcd(ab, cd) = g$ : $$\exists s, t:\; s(ab) + t(cd) = g$$
Now we have :
$$ \begin{cases} s'a + t'c =1\\ s(ab) + t(cd) = g \end{cases} \implies (s'a+t'c)(s(ab) + t(cd))= g \implies ss'a^2b + s'atcd + t'csab + tt'c^2d= g \\ \implies (ss'a^2+t'csa)b+(s'atc+tt'c^2)d=g $$ Now $z=(ss'a^2+t'csa), \; r = (s'atc+tt'c^2)$ . So they exist $z,r \in N:\; zb + rd = g$
But, does that imply that $\gcd(b, d) = g$ ?
Because we know that $\gcd(b, d)$ is the minimum linear combination of $b, d$.
We know that $\gcd(s,t) = 1 \wedge \gcd(s',t') = 1$ but I am not sure how to proceed further.

1

There are 1 best solutions below

1
On

Hint. So, $a$ and $c$ share no factors. But what about $a$ with $d$ or $c$ with $b$? What if $a$ shares factors with $d$ that $b$ doesn't, or $c$ shares factors with $b$ that $d$ doesn't? Specifically, how would that affect the values of $\gcd(ab,cd)$ versus $\gcd(b,d)$?