def euclidExtended(a, b):
    """ INPUT:  Two integers a and b with a >= b >= 0
        OUTPUT: Integers x, y, d such that d = gcd(a, b)
                and d = ax + by"""
    print ("    ", a, b) # so we can see the process.
    if b == 0:
        return 1, 0, a
    x, y, d =  euclidExtended(b, a % b) 
    return y, x - a//b*y, d


if __name__ == "__main__":
    print  ("euclidExtended(%d,%d) --> %s" % (60, 24, euclidExtended(60, 24)))
    print  ("euclidExtended(%d,%d) --> %s" % (902988, 753144, euclidExtended(902988, 753144)))
    print  ("euclidExtended(%d,%d) --> %s" % (188, 144, euclidExtended(188, 144)))
    print  ("euclidExtended(%d,%d) --> %s" % (37, 15, euclidExtended(37, 15)))
    print  ("euclidExtended(%d,%d) --> %s" % (648, 41, euclidExtended(648, 41)))
    print  ("euclidExtended(%d,%d) --> %s" % (74, 66, euclidExtended(74, 66)))