Results 1 to 2 of 2

Math Help - [SOLVED] GCD Proof: Elem. Number Theory

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    1

    [SOLVED] GCD Proof: Elem. Number Theory

    Ok, so I've tried to find out how to do this, but most of the help I could find is based on two variables a and b.

    However, I'm trying to show that for any integer a, gcd(2a + 1, 9a + 4) = 1.

    Any help would be excellent.

    Thoughts: I'm looking at using the Euclidean Algorithm, but I'm a little confused.

    SOLVED.

    For future reference to those who have the same problem, you used Euclid's Algorithm.

    9*a + 4 = 4*(2*a + 1) + (a + 1)
    2*a + 1 = 1*(a + 1) + a
    a + 1 = 1*a + 1
    a = a*1 + 0

    Therefore, the gcd is 1.
    Last edited by iMito; February 8th 2009 at 11:47 PM. Reason: Solved
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    Let d a common divisor. Then

    d|(2a+1)\Rightarrow d|(8a+4) (1)

    d|(9a+4) (2)

    From (1) and (2) d|(9a+4)-(8a+4)\Rightarrow d|a\Rightarrow d|2a (3)

    From d|(2a+1) and (3) \Rightarrow d|(2a+1)-2a\Rightarrow d|1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Elem Number Theory - gcd theorem in proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 2nd 2008, 12:16 PM
  2. Replies: 2
    Last Post: September 14th 2008, 12:14 PM
  3. number theory proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 13th 2008, 06:17 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