8
$\begingroup$

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.

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

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.

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
7
  • $\begingroup$ How come you can say that $gcd(a',d') = 1$ ? $\endgroup$ – Mario G Sep 25 '18 at 21:04
  • $\begingroup$ @MarioG Isn't it true that the gcd is 1? so $ a = a'*1 $ which is already known since g must be 1. $\endgroup$ – PossiblyDakota Sep 25 '18 at 21:12
  • $\begingroup$ @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$ $\endgroup$ – Mario G Sep 25 '18 at 21:15
  • $\begingroup$ @MarioG oh, yes. I misread it. $\endgroup$ – PossiblyDakota Sep 25 '18 at 21:18
  • $\begingroup$ "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.... $\endgroup$ – fleablood Sep 25 '18 at 23:11
0
$\begingroup$

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²

$\endgroup$

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