This question already has an answer here:

Let $a,b,c$ be integers, prove that if $\gcd(a,b) =1$ then $\gcd(ab,c) = \gcd(a,c)\times\gcd(b,c)$

I don't know what to do after I got the combinations of $ab$ and $c$.


marked as duplicate by Martin Sleziak, Did, Misha Lavrov, max_zorn, Leucippus Jan 27 at 5:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Hint: show $gcd(ab, c) | gcd(a, c)*gcd(b, c)$ and $gcd(a, c)*gcd(b, c) | gcd(ab, c)$. $\endgroup$ – Alex Wertheim Oct 23 '13 at 4:36
  • $\begingroup$ I know we can show that (a,c)(b,c) divides (ab,c) by gcd-ct $\endgroup$ – user102673 Oct 23 '13 at 4:52
  • $\begingroup$ but how do I show gcd (ab,c) divides (a,c) and (b,c) $\endgroup$ – user102673 Oct 23 '13 at 4:52
  • $\begingroup$ math.stackexchange.com/questions/535961/… $\endgroup$ – lab bhattacharjee Oct 23 '13 at 6:07

My favorite way to think about gcd's is in terms of multisets. Using the fundamental theorem of arithmetic there is a bijection from every positive integer to multisets of primes. For example, $12 = \{2,2,3\}, 49 = \{7,7\}$, and so on. Also let $1 = \emptyset$, the empty set. Then GCD's can then be looked at as the intersection of multisets. Multiplying numbers amounts to taking unions of multisets, and so on. It's $1$ if the intersection is empty. Then you can instantly see things like the fact you're proving by using set theory. In particular, if $M_a, M_b, M_c$ correspond to the multisets for $a,b,c$, then your fact amounts to showing that if $M_a \cap M_b = \emptyset$, then $(M_a \cup M_b) \cap M_c = (M_a \cap M_c) \cup (M_a \cap M_b)$, which is a standard result from an elementary proofs course! Hope that helps.


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