def extended_gcd(a: int, b: int) -> tuple:
    """
    The extended Euclidean algorithm.
    Return GCD(a, b), x and y such that:

    ax + by = GCD(a, b)

    :param a: An integer.
    :param b: An integer.
    :return: The GCD and the x and y factors of the Bézout's identity.
    """
    last_remainder, remainder = abs(a), abs(b)
    x, last_x, y, last_y = 0, 1, 1, 0

    while remainder:
        last_remainder, (quotient, remainder) = remainder, divmod(last_remainder, remainder)
        x, last_x = last_x - quotient * x, x
        y, last_y = last_y - quotient * y, y

    return (
        last_remainder,
        last_x * (-1 if a < 0 else 1),
        last_y * (-1 if b < 0 else 1)
    )