from typing import Tuple


def gcdext(a: int, b: int) -> Tuple[int, int, int]:
    """
    Extended Euclidean algorithm to compute the Greatest Common Divisor.

    Return integers g, x, y such that g = ax + by = gcd(a, b)
    """
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0