0
$\begingroup$

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.

  • 0
    @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.2012-04-28

4 Answers 4

3

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

3

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

  • 0
    The first two equations are conditions for a,b,c,d to fulfill in the original question.2012-04-29
1

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

  • 0
    (-1) This all looks irrelevant to the question, which you have not answered.2012-04-28
1

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