Extended GCD (Bezout Coefficients)

The extended Euclidean algorithm computes integers x and y such that:

a*x + b*y = gcd(a, b)

These coefficients are used to compute modular inverses and solve linear congruences.

Function signature

func ExtendedGCD(a, b int64) (g, x, y int64)

Requirements

• Return g = gcd(a, b) >= 0.
• The returned x and y must satisfy ax + by = g.
• Inputs may be zero, but not both zero.

Constraints

• |a|, |b| <= 1e12