The Extended Euclidean Algorithm and Modular Inverses

Q: 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.

Q: 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.

Q: 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.

Executive summary

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

ua + vb = gcd(a, b)

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

AlgorithmExtended Euclidean algorithmin: a, b ∈ ℤ → out: (u, v, d)

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).

Verify the invariant in production code

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.

AlgorithmModular inversionin: a, m → out: a⁻¹ mod m, or failure with a factor

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).

The productive failure

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.

Which variant to run
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.

AlgorithmRational reconstructionin: r, m → out: p/q with p/q ≡ r (mod m)

Run the extended Euclidean algorithm on (m, r) where r is the known residue.
Stop at the first step where the remainder d_i < √(m/2). Early termination is the entire trick.
Set p ← d_i and q ← the corresponding cofactor.
If gcd(p, q) = 1 and q ≤ √(m/2), return p/q; otherwise report failure.

Where this is used

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.

Handbook application: from concept to controlled practice

Purpose. This expanded section turns the original page into a practical handbook. It preserves the supplied material and adds a repeatable way to apply, check and review The Extended Euclidean Algorithm and Modular Inverses. It does not replace a contract, legislation, a controlled standard, competent engineering judgement or specialist advice.

The operating aim is to turn a compact mathematical statement into a usable chain of definitions, claims, examples and checks. Read the original explanation first, then use the workflow and checks below to convert knowledge into evidence.

Treat The Extended Euclidean Algorithm and Modular Inverses as a network of definitions and implications, not as a list of formulas. The working vocabulary on this page—section, algorithm, modular, extended, euclidean—should be made explicit before any proof or computation begins. Record the ambient set or structure, the permitted operations and the equality or equivalence relation in use. A compact theorem often changes meaning when the base field, finiteness condition, commutativity assumption or direction of an action changes.

For a proof, write the hypotheses as a checklist and mark the line at which each one is used. For a computation, state the representation of the input, the arithmetic model, the termination condition and the output invariant. For a classification problem, distinguish existence from uniqueness and distinguish an object from its representation. These separations prevent a correct local calculation from being mistaken for the general result.

A useful worked example should be small enough to inspect completely but rich enough to exercise the main mechanism. Compute the result in two ways where practical: symbolically and by substitution, structurally and numerically, or directly and through a normal form. Then include one near-miss example in which a hypothesis fails. The contrast explains why the theorem is shaped as it is and gives the reader a diagnostic pattern for later problems.

Verification is part of the mathematics. Check domains and codomains, substitute proposed solutions, test identity and zero cases, compare dimensions or cardinalities, and confirm that maps respect the required operations. In numerical work, report precision, conditioning and a residual rather than digits alone. In algorithmic work, separate mathematical correctness from implementation complexity and resource limits.

Step-by-step operating method

Fix the setting. State the objects, ambient structure, notation and assumptions before manipulating symbols.
Separate claims. Distinguish definitions, hypotheses, conclusions, equivalent conditions and consequences.
Choose a method. Select proof, construction, calculation or algorithm according to the question actually asked.
Work a small case. Use the smallest non-trivial example to expose the mechanism and test edge behaviour.
Verify independently. Substitute back, check invariants, test boundary cases or use an alternative derivation.

Worked-example protocol

Illustrative method—not a source theorem. Start with a small admissible input and list the definitions it must satisfy. Carry out each transformation on a separate line, citing the property that permits it. Preserve exact values until approximation is necessary. At the end, verify the output against the original definition and one invariant such as dimension, degree, determinant, order, norm or residual. Then alter one hypothesis and observe which step ceases to be valid. This protocol creates a reusable example without inventing a theorem-specific numerical answer.

Stage	Record	Quality check
Input	Objects, domain, notation, assumptions	Every symbol is defined
Method	Permitted operation or cited result at each step	All hypotheses hold
Output	Exact result and representation	Correct type, domain and form
Verification	Substitution, invariant or alternative derivation	Independent agreement
Boundary test	Zero, identity, degenerate or failed hypothesis	Scope is understood

Common failure modes and recovery actions

1. Watch for

Using a theorem without checking every hypothesis.

Recovery: Return to the governing definition or requirement and restate the decision in one sentence.

2. Watch for

Treating a suggestive example as a proof of the general case.

Recovery: Separate evidence from assumption, assign an owner and set a date for validation.

3. Watch for

Changing notation or conventions part-way through an argument.

Recovery: Run a small counterexample, boundary test, pilot or independent check before proceeding.

4. Watch for

Hiding a division-by-zero, convergence, finiteness or commutativity assumption.

Recovery: Record the consequence, decision and rationale, then update the controlled baseline.

5. Watch for

Reporting a computed result without a residual, substitution or structural check.

Recovery: Escalate when the issue affects safety, compliance, acceptance, material value or an agreed tolerance.

Review checklist

Can every symbol be traced to a definition or prior result?
Which hypothesis does each major step use?
Does the method cover zero, identity, degenerate and boundary cases?
Can the conclusion be checked by a second representation or calculation?
Are mandatory requirements distinguished from recommendations and illustrative values?
Are sources, assumptions, units, dates and versions recorded closely enough to reproduce the decision?
Have safety, legal, ethical, stakeholder and operational consequences been considered at the appropriate level?
Is there a named owner and a trigger for review, escalation, change or retirement?

Questions for deeper application

What is the most important distinction a practitioner must preserve when applying The Extended Euclidean Algorithm and Modular Inverses?