3
$\begingroup$

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?

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

$\: (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]

$\endgroup$
  • $\begingroup$ The downvoter should explain, as the above is correct. $\endgroup$ – Math Gems Jan 16 '13 at 3:31
  • 4
    $\begingroup$ As you well know, there is no obligation for downvoters to explain anything. $\endgroup$ – Mariano Suárez-Álvarez Jan 16 '13 at 3:37
  • 4
    $\begingroup$ @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! $\endgroup$ – Yai0Phah Jan 16 '13 at 3:42
  • 4
    $\begingroup$ 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... $\endgroup$ – Mariano Suárez-Álvarez Jan 16 '13 at 3:43
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The question is asking about the case when $\gcd(a,b)=1$, though it is somewhat unclear (I made the same mistake). $\endgroup$ – Zev Chonoles Jan 16 '13 at 3:22
  • $\begingroup$ Ah I shall adjust. $\endgroup$ – Andrew Maurer Jan 16 '13 at 3:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

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