Results 1 to 9 of 9

Math Help - *sigh*... need to prove somthing...

  1. #1
    Member
    Joined
    May 2008
    Posts
    86

    *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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by aurora View Post
    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 \gcd(ab,n)=d > 1. Then d|ab and d|n. Note \gcd(d,a)=1 since d|n and that would imply \gcd(a,n) \geq d > 1 a contradiction, so \gcd(d,a)=1. But then d|ab \implies d|b. And so \gcd(b,n)\geq d  > 1 a contradiction. Thus, d=1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by aurora View Post
    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 ra+sn=kb+\ell n=1, for some integers r,s,k,\ell. thus (kr)ab + (ksb + \ell)n=1. \ \ \square
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    86
    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by aurora View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Isomorphism View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2008
    Posts
    86
    Thank you guys
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jhevon View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Isomorphism View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Yet another polynomial problem!! sigh...
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: January 15th 2011, 07:19 AM
  2. Proof somthing...
    Posted in the Calculus Forum
    Replies: 0
    Last Post: July 13th 2010, 01:55 PM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. *sigh*... a DFQ problem.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 24th 2008, 08:19 AM
  5. sigh :( i need help
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: November 15th 2007, 08:17 AM

Search Tags


/mathhelpforum @mathhelpforum