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