// Algorithm: Extended Euclidean Algorithm
// Type: Number Theory
// Time Complexity: O(log(min(a, b)))
// Space Complexity: O(1) iterative, O(log(min(a, b))) recursive

function extendedGCD(a, b):
    if b == 0:
        return (a, 1, 0)
    gcd, x1, y1 = extendedGCD(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (gcd, x, y)