def euclid_exd(a, b):
    """
    Return a tuple (u, v, d); they are the greatest common divisor d
    of two integers a and b and u, v such that d = a * u + b * v.
    """
    if not isinstance(a, int) or not isinstance(b, int):
        raise TypeError
    u = 1
    d = a
    if b == 0:
        v = 0
        return (u, v, d)
    else:
        v_1 = 0
        v_3 = b

        while 1:
            if v_3 == 0:
                v = (d - a*u) // b
                return (u, v, d)
            q = d // v_3
            t_3 = d % v_3
            t_1 = u - q*v_1
            u = v_1
            d = v_3
            v_1 = t_1
            v_3 = t_3