Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
It is not true. Search for a counterexample. It is small. –  sdcvvc Apr 28 '12 at 11:36
4  
Consider $(3,4)$ and $(4,3)$. –  wxu Apr 28 '12 at 11:37
4  
Even smaller: $(2,1)$ and $(1,2)$. –  Asaf Karagila Apr 28 '12 at 11:43
6  
Did you try any example before asking? –  Did Apr 28 '12 at 11:43
3  
Why try it yourself when you can get it done for you here? (within 10 minutes) –  GEdgar Apr 28 '12 at 12:45

4 Answers 4

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
I don't see what the first two equations have to do with the third. –  TMM Apr 28 '12 at 14:58
    
The first two equations are conditions for a,b,c,d to fulfill in the original question. –  Gaute Apr 29 '12 at 18:01

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|improve this answer
    
(-1) This all looks irrelevant to the question, which you have not answered. –  TMM Apr 28 '12 at 15:00

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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