def egcd(a, b):
    """Computes (x, y, gcd) given a and b where x * a + y * b = gcd(a, b)"""
    # based on pseudocode found on wikipedia
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        quotient = old_r // r
        old_r, r = (r, old_r - quotient * r)
        old_s, s = (s, old_s - quotient * s)
        old_t, t = (t, old_t - quotient * t)
    return old_s, old_t, old_r