def bezout(a, b):
    """Compute the bezout algorithm of a and b, i.e. it returns u, v, p such as:

          p = GCD(a,b)
          a * u + b * v = p

       Copied from http://www.labri.fr/perso/betrema/deug/poly/euclide.html.
    """
    u = 1
    v = 0
    s = 0
    t = 1
    while b > 0:
        q = a // b
        r = a % b
        a = b
        b = r
        tmp = s
        s = u - q * s
        u = tmp
        tmp = t
        t = v - q * t
        v = tmp
    return u, v, a
