Results 1 to 6 of 6

Math Help - Number Theory GCD

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Number Theory GCD

    Let  a \in  \mathbb{Z} . with  a>0. Find the greatest common divisors below.

    a)  (a,a^n) where n is a positive integer.
    b)  (3a + 5, 7a+ 12)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by JCIR View Post
    Let  a \in \mathbb{Z} . with  a>0. Find the greatest common divisors below.

    a)  (a,a^n) where n is a positive integer.
    b)  (3a + 5, 7a+ 12)
    The answer to both is relatively straightforward. For the first, we immediately notice that the GCD is a. The second requires use of an algorithm. (3a+5, 7a+12) = (3a+5, 4a+7) = (3a+5, a+2) =
    (2a+3, a+2) = (a+1, a+2) = (a+1, 1) = 1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68
    I dont really follow the algorithm
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    The GCD of a and b, if b>a, is the same as the GCD of a and b-a. You just keep repeating that process in order to get your answer. Suppose instead I want to know (2a + 3, 6a+12). Then we get that (2a+3, 6a+12) = (2a+3, 4a+9) = (2a+3, 2a+6) = (2a+3, 3) = (2a, 3). You couldn't simplify that any further, without knowing a. In some cases the gcd would be 1 and in other cases it would be 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68
    Thanks alot that is really clear now.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    The GCD of a and b, if b>a, is the same as the GCD of a and b-a.
    More generally, the gcd of x and y divides any linear combination of x and y.

    Here, x=3a+5 and y=7a+12

    So it divides 7x-3y (to eliminate a).

    7x-3y=21a+35-21a-36=-1

    Since the gcd is an integer (and said to be positive), gcd=1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 08:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 16th 2010, 06:05 PM
  4. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum