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,408
    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, 03:28 AM
  2. [SOLVED] GCD Proof: Elem. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 9th 2009, 02:50 AM
  3. Replies: 2
    Last Post: September 14th 2008, 12:14 PM
  4. elem. numbr theory - prove P
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 5th 2008, 04:33 PM
  5. Number Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2008, 04:52 PM

Search Tags


/mathhelpforum @mathhelpforum