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.

We had a discussion in lecture recently about the greatest common denominator, and the topic came up about, given $\gcd(a, b) = 1$ and any nonzero integer $c$, whether or not $$\gcd(ab, c) = \gcd(a, c)\gcd(b, c).$$ Is this always true? We also talked about the general case $\gcd(ab, c) = \gcd(a, c)\gcd(b, c)$, and how that is not always true, but this other problem has interested me. Can anyone offer some insight?

share|improve this question
    
If $x$ and $y$ are relatively prime, this equality holds. –  tetori Jan 16 '13 at 3:22
1  
@tetori, there are no $x$s and $y$s in the question... –  Mariano Suárez-Alvarez Jan 16 '13 at 3:37
    
I edited the title. It was too easy to misunderstand the question the way it stood. –  Michael Hardy Jan 16 '13 at 3:37
    
@Mariano Suárez-Alvarez♦ Oh, it is my mistake :( –  tetori Jan 16 '13 at 4:15

4 Answers 4

up vote 7 down vote accepted

$\: (a,c)(b,c) = (a(b,c),c(b,c)) = (ab,ac,bc,cc) = (ab,(a,b,c)c), $ which $= (ab,c)$ if $\:(a,b,c) = 1$. Thus it is certainly true in your case $\:(a,b)=1,\:$ but not generally, e.g. it fails for $\:a = b = c > 1$.

Remark $\ $ We can go further to obtain a precise condition for equality:

Theorem $\quad (a,c)(b,c) = (ab,c) \iff (a,b,c,ab/(ab,c)) = 1$

Proof $\quad $ Continuing from the above calculation we have

$\begin{eqnarray}\quad (a,c)(b,c) &=&\qquad (c\ (a,b,c),ab)\ &&\ \ \text{by above} \\ &=&\, ((ab,c)\,(a,b,c),ab) &&\ \ \text {by a known gcd law [1] }\\ &=&\ \ (ab,c)((a,b,c),ab/(ab,c)) && \ \ \text{by factoring out}\ (ab,c) \end{eqnarray}$

and the above $ =\, (ab,c)$ iff the 2nd factor $= 1.\ $ QED $ $ $ $ Here's said link [1]

share|improve this answer
    
The downvoter should explain, as the above is correct. –  Math Gems Jan 16 '13 at 3:31
4  
As you well know, there is no obligation for downvoters to explain anything. –  Mariano Suárez-Alvarez Jan 16 '13 at 3:37
4  
@MarianoSuárez-Alvarez But there's etiquette in FAQ: Be honest. Above all, be honest. If you see misinformation, vote it down. Add comments indicating what, specifically, is wrong. Provide better answers of your own. Best of all — edit and improve the existing questions and answers! –  Frank Science Jan 16 '13 at 3:42
4  
This has been debated in meta. While itt is nice if people explain downvotes, they are certainly not required to, so any claims that «downvoters should» do anything are simply wrong. A downvote is a downvote: just ignore it like you'd profitably do with upvotes... –  Mariano Suárez-Alvarez Jan 16 '13 at 3:43

The answer is yes.

Let

$$\gcd(ab,c)= p_1^{\alpha_1} \cdots p_n^{\alpha_n}$$

Then for each $i$ we have

$$p_i^{\alpha_i}\mid c \,;\, p_i^{\alpha_i}\mid ab$$

Since $a,b$ are relatively prime, we get $ p_i^{\alpha_i}\mid a$ or $ p_i^{\alpha_i}\mid b$. Thus $p_i^{\alpha_i\mid \gcd(a,c)}$ or $p_i^{\alpha_i}\mid\gcd(b,c)$.

This proves that

$$\gcd(ab,c) \mid \gcd(a,c) \gcd(b,c)$$

For the other implication, the key is to observe that

$$\gcd( \gcd(a,c), \gcd(b,c)) \mid \gcd(a,b)=1$$

Since $\gcd(a,c)\mid\gcd(ab,c)$, $ \gcd(b,c)\mid\gcd(ab,c)$ and the two numbers are relatively prime, their product divides $\gcd(ab,c)$.

share|improve this answer

Consider $$a = 2 \\ b = 2 \\ c = 2 $$

share|improve this answer
    
The question is asking about the case when $\gcd(a,b)=1$, though it is somewhat unclear (I made the same mistake). –  Zev Chonoles Jan 16 '13 at 3:22
    
Ah I shall adjust. –  andybenji Jan 16 '13 at 3:23

Let $d_1=gcd(ab,c)$, $d_2=gcd(a,c)$ and $d_3=gcd(b,c)$. For any prime $p$, let $ord_p m$ denote the highest power of $p$ that divides $m$. Want to show that for any prime $p$, $ord_p d_1 = ord_p (d_2 d_3)$. It is trivial to see that $ord_p (mn)=ord_p m + ord_p n$. This means WTS $ord_p d_1 = ord_p d_2 +ord_p d_3$. Suppose there exists $p$ prime s.t.$ord_p d_1 > ord_p d_2 +ord_p d_3$ . Then if $ord_p d_1=k$ then $p^k|ab$ and $p^k|c$. Since $gcd(a,b)=1$, the first tells us that either $p^k|a$ or $p^k|b$. In the former case $p^k$ is a common divisor for $a$ and $c$ and in the latter for $b$ and $c$. This means in the former case $p^k|d_2$ implying $ord_p d_2\geq k$ clearly a contradiction, since $ord_p$ is a non-negative function and LHS>RHS. It also means, in the latter case $p^k|d_3$ implying $ord_p d_3\geq k$ a contradiction for the same reason. Suppose there exists $p$ prime s.t.$ord_p d_1 > ord_p d_2 +ord_p d_3$ . It is easy to argue that if $ord_p d_2 \neq 0$ then $ord_p d_3=0$, and the other way around. If not, you would have that for some prime $p$, $p$ divides both $d_1$ and $d_2$ and therefore, both $a$ and $b$ a contradiction. WLOG suppose $ord_p d_2=k\neq 0$. We have that $p^k|d_2$ implying $p^k|a$ and $p^k|c$. This means $p^k|ab$ and therefore $p^k|d_1$. This implies $ord_p d_1\geq k = ord_p d_2+ord_p d_3$. This is a contradiction with the fact that $ord_p d_1 > ord_p d_2 +ord_p d_3$. It follows therefore that for all primes $p$ $ord_p d_1 = ord_p (d_2 d_3)$. Therefore the equality is true.

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.