Extended Euclidean algorithm

The Extended Euclidean algorithm augments the Euclidean algorithm by preserving the linear combinations that produce each remainder. Starting with r₀ = a and r₁ = b, ordinary division generates remainders r_i+1 = r_i-1 − q_ir_i until the remainder becomes zero. The preceding nonzero remainder is gcd(a,b), and back-substitution expresses it as ax + by. These integers x and y are called Bézout coefficients, and their existence is the content of Bézout's identity.¹ The method works for negative inputs as well, although programming libraries differ in how they normalize signs and remainders. It is a constructive proof that every greatest common divisor can be represented as an integer linear combination.

The iterative form stores two coefficient pairs alongside the successive remainders, avoiding the potentially long symbolic expressions of naive back-substitution. Initialize r₀ = a, r₁ = b, with coefficient pairs (1,0) and (0,1). At each step, divide r₀ by r₁, replace the larger remainder by r₀ − qr₁, and apply the same update to both coefficient pairs. When r₁ reaches zero, the remaining remainder is the gcd and the first coefficient pair is the answer.² The number of divisions is logarithmic in the smaller input; consecutive Fibonacci numbers give a classical near-worst-case sequence for the ordinary Euclidean process.⁴

Its most common application is finding a modular inverse. If gcd(a,m) = 1, the returned coefficient x satisfies ax + my = 1, so x is an inverse of a modulo m; reducing x modulo m gives a conventional representative. If the gcd is not one, no inverse exists in the integers modulo m. The same identity solves linear Diophantine equations: ax + by = c has an integer solution exactly when gcd(a,b) divides c, after which all solutions follow from one particular solution. These operations are basic components of public-key cryptography, including the key-generation arithmetic of RSA.²³ The algorithm also appears in rational reconstruction, fraction reduction, and computer algebra.

The quotient sequence produced during the calculation is closely related to the continued-fraction expansion of a divided by b. This connection explains why the algorithm can be viewed both as remainder reduction and as a compact description of rational approximation. Implementations must also consider coefficient growth: although the remainders shrink rapidly, Bézout coefficients can temporarily become comparatively large, especially for inputs with particular quotient patterns. For very large integers, practical libraries use optimized arithmetic and may combine Euclidean reduction with faster multiplication techniques rather than treating each division as unit cost.⁵ A useful edge case is the pair (0,b): the gcd is normally taken as |b|, and a valid coefficient representation is 0·0 + 1·b when b is positive. Sign conventions should therefore be documented in software interfaces.

Bézout coefficient

An integer x or y in an identity ax + by = gcd(a,b).

Modular inverse

An integer x such that ax is congruent to 1 modulo m; it exists exactly when gcd(a,m) = 1.

Euclidean algorithm

The repeated-remainder method for computing the greatest common divisor of two integers.

Diophantine equation

An equation whose solutions are required to be integers.