# Thread: *sigh*... need to prove somthing...

1. ## *sigh*... need to prove somthing...

I'm told that gcd(a,n)=1 and gcd(b,n)=1, a,b,n are natural.
I need to prove that gcd(ab,n)=1.
I don't succeed :-\ Tried millions of things!

2. Originally Posted by aurora
I'm told that gcd(a,n)=1 and gcd(b,n)=1, a,b,n are natural.
I need to prove that gcd(ab,n)=1.
I don't succeed :-\ Tried millions of things!
Say $\displaystyle \gcd(ab,n)=d > 1$. Then $\displaystyle d|ab$ and $\displaystyle d|n$. Note $\displaystyle \gcd(d,a)=1$ since $\displaystyle d|n$ and that would imply $\displaystyle \gcd(a,n) \geq d > 1$ a contradiction, so $\displaystyle \gcd(d,a)=1$. But then $\displaystyle d|ab \implies d|b$. And so $\displaystyle \gcd(b,n)\geq d > 1$ a contradiction. Thus, $\displaystyle d=1$.

3. Originally Posted by aurora
I'm told that gcd(a,n)=1 and gcd(b,n)=1, a,b,n are natural.
I need to prove that gcd(ab,n)=1.
I don't succeed :-\ Tried millions of things!
so we have $\displaystyle ra+sn=kb+\ell n=1,$ for some integers $\displaystyle r,s,k,\ell.$ thus $\displaystyle (kr)ab + (ksb + \ell)n=1. \ \ \square$

4. Thank you very much!
However, NonCommAlg, correct me if I'm mistaken - but the fact that you find this sort of linear presentation of a and n that equals 1 doesn't mean that 1 is their gcd...

5. Originally Posted by aurora
Thank you very much!
However, NonCommAlg, correct me if I'm mistaken - but the fact that you find this sort of linear presentation of a and n that equals 1 doesn't mean that 1 is their gcd...
You are mistaken..

If gcd(n, ab) = d > 0 then d|n and d|ab => d| (kr)ab + (ksb + l)n => d|1 => d = 1

However note that NonCommAlg's trick only works for gcd of 1

6. Originally Posted by Isomorphism
You are mistaken..

If gcd(n, ab) = d > 0 then d|n and d|ab => d| (kr)ab + (ksb + l)n => d|1 => d = 1

However note that NonCommAlg's trick only works for gcd of 1
I agree. However, in my algebra class, my professor would require that you show the extra step (what you just did), so i see where aurora is coming from. i would have done it the way NonCommAlg did it. but i like the contradiction method, it seems elegant to me

7. Thank you guys

8. Originally Posted by Jhevon
I agree. However, in my algebra class, my professor would require that you show the extra step (what you just did), so i see where aurora is coming from. i would have done it the way NonCommAlg did it. but i like the contradiction method, it seems elegant to me
I like the contradiction method too. But I was telling aurora about the idea because its useful in an exam. I think its more mechanical.Contradiction may not hit at the right time

9. Originally Posted by Isomorphism
I like the contradiction method too. But I was telling aurora about the idea because its useful in an exam. I think its more mechanical.Contradiction may not hit at the right time
I agree. that's one of the reasons i like it. it is not so obvious at the moment you see the problem. NonCommAlg's way is something you would do on impulse to see how it works out, which is the charm of that method. good for tests when you can't think clearly or be fancy, but are racing against the clock and just need to get the job done