def extended_euclidean(a, b):
    """Extended Euclidean algorithm. Return s, t and r such that r = gcd(a, b)
    and s * a + t * b = r"""
    prev_r, r = a, b
    prev_s, s = 1, 0
    prev_t, t = 0, 1

    while r != 0:
        q = prev_r // r
        prev_r, r = r, prev_r - q * r
        prev_s, s = s, prev_s - q * s
        prev_t, t = t, prev_t - q * t

    return prev_s, prev_t, prev_r