# Greatest Common Divisor.

• Nov 22nd 2009, 06:47 PM
GreenDay14
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.
• Nov 22nd 2009, 07:28 PM
r0r0trog
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
• Nov 22nd 2009, 09:30 PM
GreenDay14
Quote:

Originally Posted by r0r0trog
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?
• Nov 22nd 2009, 09:54 PM
GreenDay14
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?
• Nov 23rd 2009, 12:36 AM
aman_cc
Quote:

Originally Posted by GreenDay14
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.