Extended Euclid Algorithm，euclidalgorithm,d = gcd(a, b

Extended Euclid Algorithm，euclidalgorithm,d = gcd(a, b

d = gcd(a, b) = xa + yb

GCD of a and b is the minimum positive value in the set of {xa+yb: x,ybelongs to Z}.

# extended euclid algorithm# d = gcd(a,b) = xa+yb# get gcd and the coefficientsdef extended_euclid(a, b):    if b==0:        return (a, 1, 0)    (d_low, x_low, y_low) = extended_euclid(b, a%b);    (d, x, y) = (d_low, y_low, x_low - a/b*y_low);    return (d, x, y)#该片段来自于http://byrx.net