How to show $\gcd(ac, bd) = \gcd(a,d) * \gcd(b,c)$

Question

Given that $\gcd(a,b) = 1$ and $\gcd(c,d) = 1$, show that $\gcd(ac,bd) = \gcd(a,d) * \gcd(b,c)$.

The work that I have done so far goes as follows.

We write $$\gcd(ac,bd) = acv + bdu$$ then $$\gcd(a,d) = ax + dy\quad\text{and}\quad\gcd(b,c) = bs + ct$$ and so \begin{align} \gcd(a,d) * gcd(b,c) &= (ax + dy) * (bs + ct) \\ &= axbs + axct + dybs + dyct \end{align} I tried to factor out some terms, and get $ax(bs+ct) + dy(bs+ct)$ but then I am stuck here. I don't know what else to use to prove the answer.

Answer 1

Take all prime factors in turn. We have the following relations between the multiplicities:

$$\gcd(a,b) = 1\iff\min(\alpha,\beta)=0,$$ $$\gcd(a,b) = 1\iff\min(\gamma,\delta)=0,$$

$$\gcd(ac,bd) = \gcd(a,d) \gcd(b,c)\iff\min(\alpha+\gamma,\beta+\delta)=\min(\alpha,\delta)+\min(\beta,\gamma).$$

If we consider the case $\alpha=\gamma=0$, the last identity reduces to

$$0=0+0.$$

Then with $\beta=\gamma=0$,

$$\min(\alpha,\delta)=\min(\alpha,\delta).$$ By symmetry the other cases hold.

Answer 2

Let $x = \gcd(a,d)$ and $y= \gcd(b,c)$, then $xy\mid ac$ and $xy\mid bd$ so $\boxed{xy\mid z}$ where $z=\gcd(ac,bd)$.

---

Vice versa:

We can write $a=xa'$ and $d=xd'$ where $\gcd(a',d')=1$ and $b=yb'$ and $c=yc'$ where $\gcd(b',c')=1$

Now since $z\mid ac = xya'c'$ and $z\mid bd = xyb'd'$

Now if there is prime $p$ such that $p\mid z$ and $\gcd(xy,p)=1$ then $p\mid a'c'$ and $p\mid b'd'$. If $p\mid a'$ then $p\mid b'$ since $\gcd(a',d')=1$. But then $p\mid a$ and $p\mid b$ so $p\mid \gcd(a,b)=1$ a contradiction. So there is no such $p$ and thus $\boxed{z\mid xy}$

Answer 3

Let $\gcd(a,d) = g$ so that $a = a'g$ and $d = d'g$ and $\gcd(a',d') =1$. (why?)

And let $\gcd(b,c) = h$ so that $b =b'h$ and $c= c'h$ and $\gcd(b',c') =1$ (why?).

Then $\gcd(ac,bd) = \gcd(a'c'gh, b'd'gh) = gh*\gcd(a'c',b'd')$. [$\gcd(m*k, n*k) = k\gcd(m,n)$. (why?)]

And if you take any prime factor of $a'c'$ then it is a prime factor of $a'$ or $c'$ so it is not a prime factor of either $b'$ or $d'$ (as those both coprime to both $a'$ and $c'$; $a$ and $b$ are coprime, $c$ and $d$ are coprime, and so are $a'$ and $d'$ and so are $b'$ and $c'$). So it is not a prime factor of $b'd'$. Likewise no prime factor of $b'd'$ is a prime factor of $a'c'$. So $\gcd(a'c', b'd') = 1$.

So $\gcd(ac, bd) = gh = \gcd(a,d)\gcd(b,c)$.

Answer 4

Consider (a, d) = d¹ and (b, c) = d²

In (ac, bd) we know (a, b) =1 and

(a,d) =d¹ and (c, d) =1 with (c,b)=d²

Then (ac, bd) =d¹d²