Find GCD and Bézout coefficients x, y such that ax + by = gcd(a, b).
The Extended Euclidean Algorithm not only finds gcd(a, b) but also integers x and y satisfying Bézout's identity: ax + by = gcd(a, b). These coefficients are used to compute modular inverses, solve linear Diophantine equations, and in the Chinese Remainder Theorem. The algorithm extends each step of the basic Euclidean algorithm by tracking how the GCD is expressed as a linear combination of a and b.
Bézout's identity
ax + by = gcd(a, b) for some integers x, y
No. If (x₀, y₀) is one solution, then (x₀ + k×b/gcd, y₀ − k×a/gcd) is also a solution for any integer k. The algorithm returns the pair with smallest |x|.
If gcd(a, m) = 1, then ax + my = 1. Reducing mod m gives ax ≡ 1 (mod m), so x mod m is the modular inverse of a. The extended algorithm directly computes it.