Engineering / Mathematics — Integer Algorithms
The Extended Euclidean Algorithm
Computing Bezout coefficients alongside the gcd, the recurrence for the coefficient sequences, and the size bounds that make it practical.
Executive summary
The extended algorithm tracks, at every step, how the current remainder is expressed as an integer combination of the original inputs. When the algorithm terminates, that expression is Bezout's identity for the gcd.
It is the workhorse behind modular inversion, linear congruence solving, the Chinese remainder theorem and rational reconstruction.
Learning objectives
- State the coefficient recurrences and their initial conditions.
- Bound the size of the coefficients produced.
- Apply the result to compute modular inverses.
01The algorithm
Extended Euclidean algorithm
integers a, bd = gcd(a,b) and s, t with as + bt = d- Set (r₀, s₀, t₀) = (a, 1, 0) and (r₁, s₁, t₁) = (b, 0, 1).
- While r₁ ≠ 0:
- Compute q = r₀ div r₁.
- Set (r₀, r₁) = (r₁, r₀ − q r₁).
- Set (s₀, s₁) = (s₁, s₀ − q s₁).
- Set (t₀, t₁) = (t₁, t₀ − q t₁).
- Return (r₀, s₀, t₀) with r₀ = gcd(a,b) and a s₀ + b t₀ = r₀.
O(len(a) · len(b)) bit operationsThe invariant a sᵢ + b tᵢ = rᵢ holds at every step, by induction: it holds initially, and the update applies the same linear combination to all three sequences simultaneously.
02Coefficient size
Coefficient bounds
The coefficients returned satisfy |s| ≤ b/(2d) and |t| ≤ a/(2d) where d = gcd(a,b), for inputs not in degenerate cases.
This bound is what makes the algorithm practical. The coefficients never grow beyond the size of the inputs, so no intermediate expression explosion occurs and the whole computation stays within the same order of magnitude as the inputs.
03Modular inversion
The primary application. To invert a modulo n, run the extended algorithm on (a, n). If the gcd is 1, the coefficient of a reduced modulo n is the inverse.
Modular inverse
a, n with n > 1a⁻¹ mod n, or a report that a is not invertible- Run extended Euclid on (a, n) to obtain d, s, t with as + nt = d.
- If d ≠ 1, report that no inverse exists and stop.
- Return s mod n.
O(len(n)²) bit operationsA binary extended variant avoids division entirely, mirroring the binary gcd. It is preferred on hardware where division is disproportionately expensive, and it is easier to make constant-time.
04Frequently asked questions
Is only one coefficient ever needed?
For modular inversion, yes — the coefficient of a. Implementations often omit the t sequence entirely, halving the bookkeeping, and recover t from the identity if it is ever required.
Why do the coefficients stay small?
Because they are built from the quotient sequence, and the product of all quotients is bounded by the input. Large quotients mean fast termination, so the two effects offset each other exactly.
Can this be made constant-time?
Not straightforwardly, because both the iteration count and the quotients depend on the inputs. Constant-time modular inversion in cryptographic libraries typically uses Fermat exponentiation or a fixed-iteration binary variant instead.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 58-62.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.