# GCD Proof Question

How would I prove that gcd(ab,n) = gcd(a,n)*gcd(b,n)?

-
This is not true in general. For instance, if $a = b = n = 2$ then $gcd(ab, n) = 2$ but $gcd(a, n)*gcd(b, n) = 4$. –  Adrián Barquero Oct 18 '10 at 2:14
@fmunshi: How long are you thinking about these problems before posting requesting a solution? You didn't seem to spend much with math.stackexchange.com/questions/7079/number-of-factors-proof (see especially your comment to my answer). How long did you spend with this? Did you try it out with a few examples to see if it worked out? –  Arturo Magidin Oct 18 '10 at 2:18
I think there is a typo in my textbook, I'm guessing the correct statement would be to prove gcd(ab,n) = gcd(a,n) = gcd(b,n), thats why I was struggling. –  fmunshi Oct 18 '10 at 2:23
@fmunshi:And you've been given counterexamples (easy ones! the smallest possible nontrivial one, with $a=b=n=2$). So I ask again: how long are you thinking about these problems before posting your request for a solution/help? –  Arturo Magidin Oct 18 '10 at 2:26
I hate to even point this out, but gcd(ab,n) = gcd(a,n) = gcd(b,n) is also false, in general. Just take, um, any integers with gcd(a,n) != gcd(b,n)? Bill's answer below gives what's probably the correct question... Also, I think it's considered bad form here to ask a bunch of questions without accepting answers. –  Paul VanKoughnett Oct 18 '10 at 2:50

fmunshi, it isn't true, as it was pointed out. But you can try and see what happens there when $\gcd(a,b)=1$.

-

See this recently-asked equivalent question, after imposing the correct hypotheses, e.g. $\rm \gcd(a,b,n) = 1$

Here's a proof using said hypothesis and gcd laws (associative, commutative, distributive)

$\rm\quad\quad\quad (a,n)(b,n)\ =\ (ab, n\:(a,b,n))\ =\ (ab,n)$

-