An algorithm that computes the greatest common divisor (gcd) of two integers and, simultaneously, integer coefficients u and v such that u·a + v·b = gcd(a,b). It is the Euclidean algorithm augmented to return the Bézout coefficients.

Principle

Apply repeated division with remainder to reduce a pair of integers until a remainder zero is reached, while back-substituting the divisions to express the final nonzero remainder as a linear combination of the original integers.

Demonstration

Compute gcd(99,78). Using the Euclidean steps 99 = 78·1 + 21, 78 = 21·3 + 15, 21 = 15·1 + 6, 15 = 6·2 + 3, 6 = 3·2 + 0 yields gcd = 3. Back-substitution produces coefficients: 3 = 78·14 + 99·(−11), so u = −11, v = 14 satisfy −11·99 + 14·78 = 3.

Misapplication

Attempting to use the integer algorithm unchanged on floating-point approximations or non-Euclidean rings; treating the returned coefficients as unique without noting their non-uniqueness modulo factors of the inputs.

Consequence

When applied correctly one obtains both the gcd and Bézout coefficients, enabling solutions of linear Diophantine equations, computation of modular inverses, and reductions in algorithmic number theory.

Reversal

The reversal would be searching for a factorization of the inputs from the Bézout coefficients; while coefficients give linear relations they do not directly factor numbers or replace factorization methods.

Boundary

Defined for pairs of elements in principal ideal domains and Euclidean domains (integers, univariate polynomials over a field). It does not, without adaptation, apply to arbitrary non-Euclidean rings or multivariate polynomial rings.

Semantic Tension

Differs from the plain Euclidean algorithm which returns only the gcd; the 'extended' aspect emphasizes explicit linear representation, which can be confused with algorithms that compute inverses by other means (e.g., multiplicative group methods).

Synthesis

Extended Euclidean is the Euclidean gcd procedure extended by systematic back-substitution to produce Bézout coefficients, providing both gcd and the explicit linear combination that yields it.