Utilities
Algorithms
Blankinship Algorithm
Unlike the standard method of calculating the Greatest Common Denominator (GCD) of two integers
x and y , the Blankinship algorithm also produces
the unique numbers u and
v such that
ux + vy = GCD
def Blankinship( x, y ):
gcd,u,v = 0,0,0
if x or y:
if x == 0:
gcd,v = 1,1
elif y == 0:
gcd,u = 1,1
else:
a,b,c,d = 1,0,0,1
while x>0 and y>0:
if x >= y:
q = x // y
x = x - y * q
a = a - q * c
b = b - q * d
else:
q = y // x
y = y - x * q
c = c - q * a
d = d - q * b
if x > 0:
gcd,u,v = x,a,b
else:
gcd,u,v = y,c,d
return gcd,u,v