# Prove or disprove statements about the greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other out.

(a) For all $a, b, c \in \mathbb{Z}$, $\gcd(ac, bc) = c \gcd(a, b)$

(b) For all $a, b, c \in \mathbb{Z}$, $\gcd(ab, c) = \gcd(a, b) \gcd(b, c)$

-
Try some simple examples first of all to see which you want to prove or disprove. –  anon May 15 '13 at 8:43
Unfortunately, I offer a clue without having actually tried it (this specific problem). Try seeing if they work with small integers, experiment with primes, 2,3,5, and composites, 4,6, etc. If they seem to hold, you may by now have developed a feeling for why you think it might be true, so run with that (i.e., try to prove them true). With further analysis, you may begin to feel that in fact, one is not correct, so you go back to construct a counterexample with this new perspective. And so on. –  Brady Trainor May 15 '13 at 8:45
A good general strategy with this sort of problem is to consider an arbitrary prime number $p$ and see how many times it divides both sides. If the prime always divides each side the same number of times, then the two sides are equal. Otherwise, they arent. –  C-S May 15 '13 at 8:46
Can you find a title which is more descriptive of the subject of the question? The current one essentially gives no information about your question! –  Mariano Suárez-Alvarez May 15 '13 at 8:50
Apologies, Mariano, I did what I could to make it a little bit more descriptive. –  Miguel May 15 '13 at 8:52

Hint for (a): Note that $c|ac$ and $c|bc$.

Hint for (b): Look at special cases, $a=b$, $a=c$ etc

-

I find it helpful to look at the prime factor decomposition of the numbers $a,b$ and $c$. For two numbers $x,y$ the $\gcd(x,y)$ is just the maximal set of common prime factors.

So for (a) you it is clear that the maximal sets of prime factors of $ac$ and $bc$ contain both the prime factors of $c$. So if you take the prime factors of $c$ out, both sets remain maximal.

For (b) I would suggest to play around with some examples.

-

If the highest power of prime $p$ in $a,b,c$ are $r_a,r_b,r_c$ respectively,

the highest power of $p$ in gcd$(a,b)=$min $(r_a,r_b)$

the highest power of $p$ in $c\cdot$ gcd$(a,b)=r_c+$min $(r_a,r_b)$

the highest power of $p$ in gcd$(a\cdot c,b \cdot c)=$min $(r_a+r_c,r_b+r_c)=r_c$+min $(r_a,r_b)$

the highest power of $p$ in gcd$(a\cdot b,c)=$min $(r_a+r_b,r_c)$

the highest power of $p$ in gcd$(a,b)\cdot$gcd $(b,c)=$min $(r_a,r_b)$ + min$(r_b+r_c)$

Can you prove min $(r_a+r_b,r_c)=$min $(r_a,r_b)$ + min$(r_b+r_c)?$

-

Concerning (b), perhaps it's worth mentioning that $\gcd$ and $\operatorname{lcm}$ distribute each with respect to the other, so you have \begin{align} &\gcd(\operatorname{lcm}(a, b), c) = \operatorname{lcm}(\gcd(a, c), \gcd(b, c)), \\& \operatorname{lcm}(\gcd(a, b), c) = \gcd(\operatorname{lcm}(a, c), \operatorname{lcm}(b, c)). \end{align} The first of these equalities is the correct form of (b).

-