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

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.

• Please consider using MathJax to format your question - it will make your formulas much more readable – Zubin Mukerjee Sep 25 '18 at 19:46

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.

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}$$

• What is the property you are using in the first line where $xy|ac$ and $xy|bd$ so $xy|z$ ? – Mario G Sep 25 '18 at 20:04
• $xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them. – greedoid Sep 25 '18 at 20:06
• The greatest common divisor is a multiple of every other common divisor. – PossiblyDakota Sep 25 '18 at 20:08

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)$$.

• How come you can say that $gcd(a',d') = 1$ ? – Mario G Sep 25 '18 at 21:04
• @MarioG Isn't it true that the gcd is 1? so $a = a'*1$ which is already known since g must be 1. – PossiblyDakota Sep 25 '18 at 21:12
• @PossiblyDakota The only gcd that is known is $gcd(a,b) = 1$ and $gcd(c,d) = 1$ That is not the $gcd(a,d) = 1$ – Mario G Sep 25 '18 at 21:15
• @MarioG oh, yes. I misread it. – PossiblyDakota Sep 25 '18 at 21:18
• "How come you can say that gcd(a′,d′)=1" Because it is. And I say "why" because I want you to work it out for yourself. But... see next comment.... – fleablood Sep 25 '18 at 23:11

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²