The GCD plus a certificate of how it was formed
Bézout's identity states that gcd(a, b) can be written as ua + vb for integers u, v. The extended Euclidean algorithm produces these coefficients at essentially no extra asymptotic cost by carrying two auxiliary sequences through the same quotient sequence. The immediate payoff is modular inversion; the deeper payoff is rational reconstruction, which recovers a rational number from its image modulo a large integer.
Learning objectives
- State Bézout's identity and the size bounds on its coefficients.
- Carry the correct loop invariants through an extended GCD implementation.
- Compute a modular inverse and detect when none exists.
- Choose the half-extended variant when only one coefficient is needed.
- Apply rational reconstruction to lift a modular result back to ℚ.
Section 01Bézout's identity
For integers a, b not both zero there exist u, v with
The coefficients are not unique: adding a multiple of b/d to u and subtracting the corresponding multiple of a/d from v gives another solution. The algorithm returns the minimal pair, satisfying |u| ≤ b/(2d) and |v| ≤ a/(2d). These bounds matter: they guarantee no coefficient explosion, which is exactly the failure mode a naive implementation would produce.
Section 02The algorithm and its invariants
- Set (u, v, d) ← (1, 0, a) and (u', v', d') ← (0, 1, b).
- While d' ≠ 0:
- Set q ← ⌊d / d'⌋.
- Set (u, v, d, u', v', d') ← (u', v', d', u − qu', v − qv', d − qd').
- Invariant: ua + vb = d and u'a + v'b = d' hold at every step.
- Return (u, v, d) with ua + vb = d = gcd(a, b).
Checking u·a + v·b == d before returning costs two multiplications and catches essentially every implementation error in this routine, including sign errors and off-by-one updates. In a subject where wrong answers are plausible, this check is cheap insurance.
Section 03Modular inverse
The inverse of a modulo m exists precisely when gcd(a, m) = 1. Running the extended algorithm on (a, m) gives ua + vm = 1, and reducing modulo m gives ua ≡ 1, so u is the inverse.
- Run the extended Euclidean algorithm on (a mod m, m) to obtain (u, v, d).
- If d ≠ 1, report that no inverse exists. d is then a non-trivial factor of m — useful information, not merely an error.
- Return u mod m, normalised to the range [0, m).
Several factoring methods — Pollard’s ρ, p−1, and the elliptic curve method — work by deliberately provoking a failed inversion. Code in this domain should surface the offending GCD rather than raising a generic exception.
Section 04Half-extended and cost control
Often only one coefficient is wanted. Modular inversion needs u and discards v; the half-extended variant simply omits the v sequence, saving one multiplication and one subtraction per iteration together with the associated storage. On multiprecision operands this is a measurable saving.
| Goal | Variant | Sequences carried |
|---|---|---|
| GCD only | Plain Euclid | Remainders only |
| Modular inverse | Half-extended | Remainders and u |
| Full Bézout identity | Fully extended | Remainders, u and v |
| Diophantine equation ax + by = c | Fully extended | Remainders, u and v, then scale by c/d |
| Rational reconstruction | Half-extended with early exit | Remainders and u, stopped by size |
For the Diophantine equation ax + by = c, a solution exists if and only if d = gcd(a, b) divides c; then scaling the Bézout pair by c/d gives one solution, and the general solution adds integer multiples of (b/d, −a/d).
Section 05Rational reconstruction
Modular algorithms compute a result modulo a large integer m and then need to recover a rational number from it. If the true answer is x = p/q with |p|, q both smaller than √(m/2), it is uniquely recoverable — and the extended Euclidean algorithm recovers it.
- Run the extended Euclidean algorithm on (m, r) where r is the known residue.
- Stop at the first step where the remainder di < √(m/2). Early termination is the entire trick.
- Set p ← di and q ← the corresponding cofactor.
- If gcd(p, q) = 1 and q ≤ √(m/2), return p/q; otherwise report failure.
Rational reconstruction closes the loop on modular methods. A linear system is solved modulo several primes, the results are combined by the Chinese remainder theorem, and the rational solution is reconstructed — avoiding the coefficient explosion that direct rational elimination would cause.
ReferenceFrequently asked questions
Why are the Bezout coefficients bounded?
Because the auxiliary sequences grow in a controlled way governed by the same quotients that shrink the remainders. The product of the growth in the cofactors and the shrinkage in the remainders is essentially constant, which yields the standard bounds and guarantees no intermediate expression swell.
What does a failed modular inverse tell me?
That the GCD of the operand and the modulus is greater than 1 — and that GCD is a non-trivial factor of the modulus. Several factoring algorithms are built entirely around engineering this situation, so treat it as data rather than as an exception.
Is rational reconstruction always unique?
It is unique when the numerator and denominator are both bounded by the square root of half the modulus. Outside that range multiple rationals share the same residue and the reconstruction is ambiguous, so the size condition must be checked, not assumed.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
Knuth volume 2 and Cohen's GTM 138 both treat the extended algorithm and its variants; rational reconstruction is covered in the computer algebra literature, notably von zur Gathen and Gerhard.
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.