def ext_gcd(a, b):
    """
    Extended Euclidean Algorithm. Find the result for ax + by = gcd(a, b).

    Parameters
    ----------
    a: int
    b: int
    """
    if b == 0:
        return 1, 0
    elif a % b == 0:
        return 0, 1
    else:
        x, y = ext_gcd(b, a % b)
        return y, x - y * (a // b)