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

Is it true that $\gcd(a,bc)=\gcd(a,b)\gcd({a\over\gcd(a,b)}, c)$?

It is true in quite a few examples that I came up with, e.g.

$a = 18, b = 21, c = 33$
$\gcd(18,21)\gcd({18\over\gcd(18,21)}, 33) = 3 \gcd({18 \over 3}, 33) = 3 \times 3 = 9$
$\gcd(18,693) = 9$

Here is my (probably not very good) attempt at a proof:

For a $b$ where $\gcd(a, b) = 1$
For a $c$ where $\gcd(a, c) = 1$

$\gcd(k_1a, k_1b) = k_1$
$\gcd(k_2a, k_2c) = k_2$

$\gcd(k_1k_2a, k_1k_2bc) = k_1k_2$

Hence, $\gcd(k_1k_2a, k_1b) \gcd({k_1k_2a \over \gcd(k_1k_2a, k_1b)}, k_2b) = k_1 \gcd({k_1k_2a \over k_1}, k_2c) = k_1k_2 = \gcd(k_1k_2a, k_1k_2bc)$

Is this statement true, or did I just stumble across several lucky coincidences?

share|cite|improve this question
You can work on this one prime at a time. Assume $p$ is prime, $a=p^r$, $b=p^s$, $c=p^t$, evaluate both sides under all possible order relations among $r$, $s$, and $t$. – Gerry Myerson May 27 '13 at 12:45
up vote 2 down vote accepted

It is generally true (for positive arguments) that $\gcd(dx,dy)=d\gcd(x,y)$. Now $d=\gcd(a,b)$ divides both $a$ and $b$, so you get from this that $$ \gcd(a,bc)=d\gcd(a/d,(b/d)c). $$ Moreover $a/d$ and $b/d$ are relatively prime (a common divisor, multiplied by $d$, would divide both $a$ and $b$, and this can only happen for $1$). So what you are asking boils down to: if $a'$ and $b'$ are relatively prime, does it hold for all $c$ that $\gcd(a',b'c)=\gcd(a',c)$? The answer is yes, this is a well known fact attributed to Gauss.

share|cite|improve this answer
Thanks Marc, great explanation :) – PartiallyFinite May 28 '13 at 5:37

Yes, by basic gcd laws (distributive, commutative, associative, etc) we have $$(a,b)\left(\frac{a}{(a,b)},c\right) = (a,(a,b)c) = (a,ac,bc) = (a(1,c),bc) = (a,bc) $$

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.