##  [Extended Euclidean Algorithm](/extended-euclidean-algorithm-1) 

 Definition

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

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

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

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

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

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

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

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

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.