# To find the pairs of Bézout numbers for the integers (a,b),
# we apply the extended Euclidean algorithm:
# 1 x a + 0 x b = a
# 0 x a + 1 x b = b
# (u-q*x) * a + (v-q*y) * b = d
def xgcd(a,b):
u = 1; v = 0
x = 0; y = 1
print u, '*', a, '+', v, '*', b, '=', a
mema = a
memb = b
while b:
q = a//b
x, u = u - q*x, x
y,v = v - q*y,y
a, b = b, a % b
print u, '*', mema, '+', v, '*', memb, '=', a
return a , u, v