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?

  • 3
    $\begingroup$ 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$. $\endgroup$ – Gerry Myerson May 27 '13 at 12:45

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.

  • $\begingroup$ Thanks Marc, great explanation :) $\endgroup$ – Greg 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) $$


Your Answer

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

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