Is $\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$?

2,164

Solution 1

No, let $a= 2, b=3, c=3, d= 2$, then $\gcd(a,b) = 1 = \gcd(c,d) = \gcd(a,c) = \gcd(b,d)$, but $\gcd(ac, bd) = 6$.

Solution 2

Even if you demand that the numbers $a, b, c, d$ are all different, it is trivial to find a counterexample:

$$\begin{align} \gcd(1,6) &= 1; \\ \gcd(2,3) &= 1; \\ \gcd(1,2) \cdot \gcd(6,3) &\neq \gcd(1 \cdot 6, 2 \cdot 3). \end{align}$$

Solution 3

It is not true generally. By using simple gcd arithmetic, employing only basic universal gcd laws (associative, commutative, distributive laws), we can determine precisely when it holds true and, hence, easily construct counterexamples.

Theorem $\ $ If $\rm\:(a,c)=1=(b,d)\:$ then $\rm\:(ac,bd) = (a,b)(c,d)\!\iff\! (a,d) = 1 = (b,c) $

Proof $\ $ We apply the Lemma below a few times to compute gcd products.

Notice $\rm\: (ac,bd) = (a,bd)(c,bd)\ $ by $\rm\:(a,c)=1\:\Rightarrow (a,c,bd)=1$

Further $\rm\:(a,bd) = (a,b)(a,d)\ $ since $\rm\ (b,d) = 1\:\Rightarrow (a,b,d) = 1$

Further $\rm\:(c,bd) = (c,b)(c,d)\ $ since $\rm\ (b,d) = 1\:\Rightarrow (c,b,d) = 1$

Hence $\rm\: (ac,bd) = (a,\!bd)(c,\!bd) = (a,b)(a,d)(c,b)(c,d)\ $ by combining the above.

Hence $\rm\: (ac,bd) = (a,\:b)\:(c,\:d)\ \iff\ (a,d)\:(c,b) = 1\ $ by comparing with prior. $\ $ QED

Lemma $\rm\ (x,y)(x,z) = (x,yz)\ \ if\ \ (x,y,z) = 1$

Proof $\rm\quad (x,y)(x,z) = (xx,xy,xz,yz) = (x(x,y,z),yz) = (x,yz)\ \ \ $ QED

Solution 4

gcd is a multiplicative function , so:

If $\gcd(a,c)=1$ then $\gcd(ac,bd)=\gcd(a,bd)\cdot \gcd(c,bd)$

and :

If $\gcd(b,d)=1$ then $\gcd(ac,bd)=\gcd(b,ac)\cdot \gcd(d,ac)$

Share:
2,164

Related videos on Youtube

Sayantan
Author by

Sayantan

Updated on April 30, 2020

Comments

  • Sayantan
    Sayantan over 3 years

    Let $a$,$b$,$c$ and $d$ be four natural numbers such that $\gcd(a,c)=1$ and $\gcd(b,d)=1$. Then is it true that,$$\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$$ I'm awfully weak in number theory. Can anyone please help? Thank you.

    • sdcvvc
      sdcvvc over 11 years
      It is not true. Search for a counterexample. It is small.
    • wxu
      wxu over 11 years
      Consider $(3,4)$ and $(4,3)$.
    • Asaf Karagila
      Asaf Karagila over 11 years
      Even smaller: $(2,1)$ and $(1,2)$.
    • Did
      Did over 11 years
      Did you try any example before asking?
    • GEdgar
      GEdgar over 11 years
      Why try it yourself when you can get it done for you here? (within 10 minutes)
    • Sayantan
      Sayantan over 11 years
      @GEdgar : I admit that I did not look for any counterexample and when I was posting this question I was thinking something similar to what you have said in your comment. Actually, this came from some different problem. Anyway, I apologize for the whole mess. Regrads.
    • N. S.
      N. S. over 11 years
      It is easy to prove that $\gcd(a,b)\gcd(c,d) | \gcd(ac,bd)$
    • Asaf Karagila
      Asaf Karagila over 11 years
      @Sayantan: Here's a good advice for any field of mathematics which you study, if you don't meddle with things by hand and chew on the problems you will have a hard time to grasp the material. Most of the introductory level courses give problems in order to exercise the use of definitions; theorems; and practice writing correct proofs. When approaching a problem you should have all your definitions and theorems at hand and you need to read again all the definitions of things appearing in your exercise and all the theorems about them which seem relevant. The answer should appear from that.
  • TMM
    TMM over 11 years
    I don't see what the first two equations have to do with the third.
  • TMM
    TMM over 11 years
    (-1) This all looks irrelevant to the question, which you have not answered.
  • Gaute
    Gaute over 11 years
    The first two equations are conditions for a,b,c,d to fulfill in the original question.
  • Bill Dubuque
    Bill Dubuque about 3 years
    See also here