Extended Euclidean Algorithm
Propagate Euclidean remainders backward to find coefficients satisfying ax + by = gcd(a, b).
Core idea
Euclid's remainder chain preserves the gcd. Extended Euclid also substitutes equations backward so the same gcd becomes a linear combination of the original inputs.
Read the visualization
Rows descend through quotients and remainders to the zero base case, then fill coefficient columns in reverse order during unwinding.
| a | b | q | x | y | |
|---|---|---|---|---|---|
| number 0 level | |||||
| number 1 level | |||||
| number 2 level | |||||
| base case |
Begin the Euclidean division chain while tracking coefficient equations.
1function extGcd(a: number, b: number): [number, number, number] {
2 if (b === 0) // base case: gcd = a
3 return [a, 1, 0]; // a·1 + 0·0 = a → (x,y)=(1,0)
4 const q = Math.floor(a / b); // down down: one step down
5 const [g, x1, y1] = extGcd(b, a % b); // recursion compute down level
6 return [g, y1, x1 - q * y1]; // back substitute: (x,y) = (y', x'−q·y')
7}
compute30·x + 18·y = gcd
gcd6
1 / 9
Complexity and tradeoffs
Time: O(log min(a,b)). Space: O(1) iterative. Bezout coefficients provide modular inverses whenever the gcd is one.
Invariant: Every completed row's coefficients express its gcd as a linear combination of that row's two inputs.
Where it fits
Bezout coefficients solve linear Diophantine equations and provide modular inverses, which are the key construction step in the Chinese Remainder Theorem.