Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.