Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – 6005 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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.