Results 1 to 4 of 4

Math Help - Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    40

    Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

    Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

    Any help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    GCD

    Hello qtpipi
    Quote Originally Posted by qtpipi View Post
    Suppose gcd(a,b) = 1, prove gcd(na,nb) = n

    Any help?
    n is a common divisor of na and nb. Suppose now that \gcd(na, nb) = m > n. Then, since every common divisor of na and nb is a divisor of \gcd(na, nb), n|m \Rightarrow np = m, for some p > 1

    \Rightarrow np | na

    \Rightarrow p|a and

    np|nb \Rightarrow p|b.

    So p is a common divisor of a and b. Contradiction, since \gcd(a,b)=1.

    Therefore gcd(na, nb) = n.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    40
    Thank you thank you!

    I have another similar problem:

    Prove that gcd(a+b, a-b) = gcd(2a, a-b) = gcd(a+b, 2b)

    Any help with this one too??? Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2009
    Posts
    40
    Nevermind I figured it out!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: March 2nd 2011, 01:36 AM
  2. Prove: Suppose |H|<∞. then
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 9th 2009, 12:00 AM
  3. Suppose that b<=L+e for all e>0. Prove b<=L
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 4th 2009, 01:02 AM
  4. Replies: 1
    Last Post: March 20th 2009, 06:38 AM
  5. Replies: 0
    Last Post: May 1st 2008, 04:11 PM

Search Tags


/mathhelpforum @mathhelpforum