def bezout(a, b):
    if b == 0:
        return (1,0)
    else:
        (u,v) = bezout(b,a%b)
        return (v, u-(a//b)*v)