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$
  • 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$
  • $\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$
  • $\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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