The extended Euclidean algorithm is an algorithm that, given two integers and , computes their nonnegative greatest common divisor and integers such that
It extends the Euclidean algorithm by tracking how each successive remainder can be expressed in terms of the original inputs. The resulting coefficients, called Bézout coefficients, provide a constructive form of Bézout's identity. The method is fundamental in computational number theory, especially for finding modular inverses and solving integer equations.
Mathematical basis
For nonnegative integers with , division with remainder gives
The key identity is
Indeed, an integer divides both and if and only if it divides both and .
Repeated division therefore produces a sequence of decreasing nonnegative remainders. The last nonzero remainder is the greatest common divisor.
The extended algorithm adds an observation: every new remainder is an integer linear combination of the previous two. Since the initial values are already linear combinations of and ,
every later remainder can also be expressed as . Tracking the coefficients eventually expresses the greatest common divisor in this form.
The underlying division procedure appears in Books VII and X of Euclid's Elements, for integers and magnitudes respectively. The extended procedure retains the same divisions while adding coefficient bookkeeping.
Recurrence and implementation
For positive inputs, initialize
At each step, compute
and update
These recurrence relations preserve
When the next remainder is zero, the current nonzero remainder and its coefficients give the answer.
The following iterative version handles negative inputs by applying the divisions to their absolute values:
extended_gcd(a, b):
old_r, r = abs(a), abs(b)
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q*r
old_s, s = s, old_s - q*s
old_t, t = t, old_t - q*t
if a < 0:
old_s = -old_s
if b < 0:
old_t = -old_t
return old_r, old_s, old_t
Each paired assignment is simultaneous: both right-hand expressions use the values from before the assignment.
For a single zero input, the procedure returns the absolute value of the other input and suitable coefficients. Under the common convention , it also returns a valid identity for , although some treatments leave that greatest common divisor undefined.
Worked example
For and , the Euclidean divisions are
Thus .
Tracking coefficients gives:
| Remainder | Coefficient of | Coefficient of |
|---|---|---|
The output is therefore
with
The same coefficients can be found by back-substitution, starting at the last nonzero remainder:
Back-substitution and forward coefficient tracking are two implementations of the same algebraic process.
Correctness
Correctness follows from three properties.
Preservation of the greatest common divisor. Each replacement
leaves the common divisors unchanged.
Preservation of the coefficient identity. If
then
Thus every stored remainder has the claimed representation.
Termination. The nonzero remainders form a strictly decreasing sequence of positive integers, so eventually a remainder is zero.
At termination, the last nonzero remainder has the same greatest common divisor as the inputs and is itself that divisor. Its stored coefficients establish the required identity.
Matrix interpretation
A single update can also be written using a matrix:
The update matrix has determinant , so its inverse also has integer entries. Applying the same matrix to the coefficient rows explains why remainder computation and coefficient tracking stay synchronized.
Applications
Modular inverses
In modular arithmetic, an integer has a multiplicative inverse modulo exactly when
If the algorithm finds
then reduction modulo gives
Thus is an inverse of .
For example,
so the inverse of modulo is
If the computed gcd exceeds , no inverse exists.
Modular inversion is used in computational algebra and cryptography, including arithmetic underlying public-key systems.
Linear Diophantine equations
A linear Diophantine equation
with not both zero has an integer solution if and only if
divides .
If the algorithm gives
then one solution is
All integer solutions are
In particular, Bézout coefficients are generally not unique. For , this formula describes all coefficient pairs representing the gcd.
Congruences and the Chinese remainder theorem
A congruence
is equivalent to an integer equation
The extended algorithm therefore determines whether it is solvable and constructs solutions.
It also supplies the modular inverses used in constructive proofs and implementations of the Chinese remainder theorem. For noncoprime moduli, a gcd calculation determines whether the congruences are compatible.
Efficiency and implementation limitations
Let
measure the input size in bits. The standard algorithm uses Euclidean division steps, expressed in big-O notation. Consecutive members of the Fibonacci sequence give worst-case division counts for a given input magnitude.
The division count is not the same as the bit-operation cost. With classical integer arithmetic, a standard implementation has bit complexity. Faster divide-and-conquer variants can achieve bounds of the form
where denotes the cost of multiplying -bit integers.
The iterative implementation stores only a fixed number of integers, but their bit lengths grow with the input size; its storage is therefore not constant when measured in bits.
Practical limitations include:
- Overflow: intermediate coefficient products can exceed a fixed-width integer type even when the final result fits.
- Signed division conventions: using nonnegative remainders avoids differences between programming languages' rules for negative division.
- Timing leakage: the ordinary algorithm's iteration count and branches depend on its inputs. Cryptographic uses involving secrets may require specialized constant-time implementations.
Generalizations
The method extends beyond integers to a Euclidean domain, where division with a suitably decreasing remainder measure is available.
An important example is the ring of polynomials over a field. Given polynomials and , the extended algorithm computes polynomials satisfying
where is a greatest common divisor. Since polynomial gcds are determined only up to multiplication by a nonzero field element, they are usually normalized to be monic.
If is irreducible and is not divisible by , normalizing the identity to
makes an inverse of modulo . This provides an effective inversion method in polynomial representations of finite fields.
The existence of a gcd alone does not guarantee that the extended procedure applies in an arbitrary ring: the Euclidean algorithm additionally requires a suitable division-with-remainder operation.