Results 1 to 5 of 5

Math Help - Greatest Common Divisor.

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    81

    Greatest Common Divisor.

    Hey guys, I got a simple question here asking to find the greatest common divisor of a and b in the form ma+mb

    the values given are a= -3719 and b = 8416. I am having a bit of trouble working these out when b is greater then a, i know that:
    -3719|8416=1=... I think?

    Could someone help me here please. Thanks a lotl.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    you're right that gcd(3719, 8416) = 1.
    now use the extended euclidean algorithm to get it on the form na + mb = 1.
    Extended Euclidean algorithm - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    81
    Quote Originally Posted by r0r0trog View Post
    you're right that gcd(3719, 8416) = 1.
    now use the extended euclidean algorithm to get it on the form na + mb = 1.
    Extended Euclidean algorithm - Wikipedia, the free encyclopedia
    Thanks, I should have included that I went that far as well. i understand the algorithm (ax+by=gcd(a,b)), but where is the x and y coming from?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2008
    Posts
    81
    Also I have a second one: a= 1575 and b=231, which ii worked out the gcd to be 21, but how do i express that in ma+nb?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by GreenDay14 View Post
    Also I have a second one: a= 1575 and b=231, which ii worked out the gcd to be 21, but how do i express that in ma+nb?
    As a previous post suggested - ma+nb form comes directly from the euclidean algorithm - by repeated substitution. Plz have a look at the suggested wiki article and post any specific question that you might have.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 06:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 08:16 PM
  4. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 04:24 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2008, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum