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
    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))