def euclid(a, b):
    """ Finds x and y such that ax + by = gcd(a,b)
        Returns the tuple (gcd(a,b), x, y)
    """
    last_b1, b1 = 1, 0
    last_b2, b2 = 0, 1
    last_b3, b3 = a, b
    while b3 != 0:
        q = last_b3 // b3
        last_b1, b1 = b1, last_b1 - q * b1
        last_b2, b2 = b2, last_b2 - q * b2
        last_b3, b3 = b3, last_b3 - q * b3

    return last_b3, last_b1, last_b2