GCD with Bezout Coefficients

Bézout's identity and the extended Euclidean algorithm

Bézout's identity states that for any integers a, b there exist integers x, y such that a · x + b · y = gcd(a, b). The extended Euclidean algorithm computes the GCD together with these coefficients: it runs the standard Euclidean recursion gcd(a, b) = gcd(b, a mod b) and back-substitutes the remainders to recover x and y. Example: gcd(15, 12) = 3 with 15 · 1 + 12 · (−1) = 3. The coefficients are not unique — adding k · (b/gcd) to x and subtracting k · (a/gcd) from y gives another valid pair. The algorithm still runs in O(log min(a, b)).

Cryptographic and algorithmic uses

• Modular inverse — essential for RSA: d ≡ e^(−1) (mod φ(n)) is exactly the Bézout coefficient of e.
• Linear Diophantine equations ax + by = c are solvable iff gcd(a, b) | c; the extended algorithm produces one solution.
• Chinese Remainder Theorem — the constructive proof uses Bézout coefficients to combine congruences with coprime moduli.
• Network and graph algorithms — shortest-path problems with negative weights (Bellman–Ford) and cycle-detection routines use related GCD-based reasoning.

FAQ

Are the Bézout coefficients unique? No. Given one pair (x, y), every (x + k · b/g, y − k · a/g) with integer k and g = gcd(a, b) is also valid.

Can the coefficients be negative? Yes — at least one of x and y is typically negative when both a, b > 0.

When does the modular inverse a^(−1) mod n exist? Only when gcd(a, n) = 1. The extended algorithm then returns coefficients with a · x + n · y = 1, so x mod n is the inverse.

Is there a binary version? Yes — the binary extended GCD avoids division and uses only shifts and subtractions, useful in hardware and constant-time cryptographic implementations.