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.

  • 2
    Please consider using MathJax to format your question - it will make your formulas much more readable – Zubin Mukerjee Sep 25 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


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 at 20:04
  • $xy$ divide $ac$ and $bd$ so it must divide the greates common divisor of them. – greedoid Sep 25 at 20:06
  • The greatest common divisor is a multiple of every other common divisor. – PossiblyDakota Sep 25 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 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 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 at 21:15
  • @MarioG oh, yes. I misread it. – PossiblyDakota Sep 25 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 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²

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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