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.

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

share|improve this question
1  
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
8  
@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
6  
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
show 4 more comments

3 Answers

up vote 4 down vote accepted

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

share|improve this answer
add comment

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)$

share|improve this answer
add comment

It would be difficult, as it is not true. Take a=b=n=2

share|improve this answer
add comment

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.