Results 1 to 5 of 5

Math Help - Elem Number Theory - gcd theorem in proof

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    Elem Number Theory - gcd theorem in proof

    ok - so after a long proof that I know is correct, I have come to conclude that:
    given: gcd(2a+b, a+2b) = 1 or 2 or 3
    I have to prove that this does not equal 2.

    I also know (and have proven) that gcd(a,b)=1.

    I know I need to show that for d to not equal 2, I would have to pretend and show that when d equals 2, d could not equal 1 - which is false since d has to equal 1.
    So to start: Assume gcd(2a+b, a+2b) = 2, then it divides both a and b

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

  2. #2
    Member
    Joined
    Aug 2008
    Posts
    80
    Hello,

    If 2a+b is even, so is b.
    If a+2b is even, so is a.
    This contradicts gcd(a, b)=1.

    Bye.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    but I need to contradict that it equals 2, not 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,410
    Thanks
    1
    He did. Reiterating what wisterville said, if the gcd of both numbers is 2, then that must mean they are both even. Since 2a + b is even, then so must b (even + even = even) and a + 2b being even also implies a is even.

    So, 2 is a common factor of both a and b which contradicts that their gcd was 1 which you were given. So, our initial assumption that (2a+b, a+2b) = 2 was wrong.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ah! got it! thank you - that makes sense

    (sorry for the lack of comprehension a minute ago)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number Theory Question (Mobius Theorem)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 7th 2011, 02:28 AM
  2. [SOLVED] GCD Proof: Elem. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 9th 2009, 01:50 AM
  3. Replies: 2
    Last Post: September 14th 2008, 11:14 AM
  4. elem. numbr theory - prove P
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 5th 2008, 03:33 PM
  5. Number Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2008, 03:52 PM

Search Tags


/mathhelpforum @mathhelpforum