The Extended Euclidean Algorithm

Suppose you want a single equation expressing $\gcd(240, 46)$ as an integer combination of $240$ and $46$ . The ordinary Euclidean Algorithm tells you the gcd is $2$ . But it does not, by itself, hand you integers $x$ and $y$ with $240x + 46y = 2$ . Bezout's Identity guarantees such $x, y$ exist. However, existence proofs are often non-constructive in spirit, even when the underlying algorithm is finite. The Extended Euclidean Algorithm closes this gap. It runs the same division steps as the ordinary algorithm. Along the way, it records enough bookkeeping data. It then unwinds that data to produce explicit Bezout coefficients. This is not a cosmetic upgrade. The coefficients themselves are the object of interest in an enormous range of applications. Solving a Linear Congruence $ax \equiv b \pmod n$ reduces to finding a Bezout pair for $a$ and $n$ . Computing a Modular Inverse of $a$ modulo $n$ is nothing more than this. It is the cornerstone of modular arithmetic, the RSA cryptosystem, and the Chinese Remainder Theorem. It amounts to reading off the coefficient of $a$ in a Bezout identity with $n$ . Without an explicit algorithm, one would be reduced to search or guesswork. With it, the computation is as mechanical as long division, and just as fast. The big picture is that number theory has two layers. There are existence statements: there is a gcd, there are Bezout coefficients. And there are constructive procedures that realize those statements as finite computations. The Euclidean Algorithm itself already exemplifies this for the gcd. The Extended Euclidean Algorithm does the same job one level up. It works for the linear combination witnessing that gcd. It is the bridge between the abstract identity $\gcd(a,b) = ax + by$ and a concrete pair $(x,y)$ . That pair is one you can write down and verify. This article gives the precise algorithm. It proves the algorithm terminates and is correct. It works two genuinely asymmetric examples by hand. It shows exactly which hypothesis makes the whole machine run: finiteness of the division chain, and integrality of the remainders. It closes by connecting the coefficients directly to modular inverses and linear congruences, the natural next topics.

Key takeaways

The ordinary Euclidean Algorithm computes $\gcd(a,b)$ ; the extended version also computes integers $x, y$ with $ax + by = \gcd(a,b)$ .
It works by running the division algorithm forward, then substituting back through the chain of remainders from the last nontrivial step to the first.
Equivalently, one can carry a pair of auxiliary sequences forward alongside the remainders, avoiding an explicit back-substitution pass.
The algorithm terminates in $O(\log \min(a,b))$ division steps, the same bound as the ordinary Euclidean Algorithm.
Bezout coefficients are never unique; the algorithm produces one particular solution, and all others differ by multiples of $b/\gcd(a,b)$ and $a/\gcd(a,b)$ .
Its main downstream use is computing modular inverses: if $\gcd(a,n)=1$ , the $x$ produced satisfies $ax \equiv 1 \pmod n$ .
Key idea: run Euclid's division steps forward to reach the gcd, then substitute backward to express that gcd as an explicit integer combination of the original two numbers.

Where this lives today

The Extended Euclidean Algorithm is the standard method for computing multiplicative inverses modulo $n$ , which underlies the RSA cryptosystem's key generation (computing the private exponent as the inverse of the public exponent modulo $\varphi(n)$ ) and virtually all modular-arithmetic-based cryptography, including elliptic curve arithmetic over finite fields. In computer algebra systems, the polynomial analogue of the same algorithm computes greatest common divisors and partial-fraction-style decompositions of rational functions. In the Chinese Remainder Theorem, reconstructing a residue from several congruences requires exactly the Bezout coefficients this algorithm supplies. It is also the standard route to solving general linear congruences $ax\equiv b\pmod n$ , and more generally linear Diophantine equations $ax+by=c$ , whenever $d=\gcd(a,b)$ divides $c$ : scale the algorithm's Bezout pair by $c/d$ . In lattice-based algorithms and continued fraction theory, the coefficient sequences $s_i, t_i$ are exactly the numerators and denominators of the convergents of the continued fraction expansion of $a/b$ , linking this elementary algorithm to Diophantine approximation.

Ask the tutor: How do I use the Bezout coefficients from this algorithm to solve a general linear congruence $ax \equiv b \pmod n$ ?

a, b

Intuition

Picture the Euclidean Algorithm as a staircase descending from $a$ and $b$ down to $\gcd(a,b)$ , one remainder at a time. Each step of the staircase is a division equation, and each equation is a small, exact bookkeeping fact: it says one remainder is a specific integer combination of the two remainders just above it. The ordinary algorithm only cares about the value $r_i$ at each step, and eventually reports $r_k$ , the gcd. The extended algorithm insists on remembering the recipe — the exact combination of $r_{i-2}$ and $r_{i-1}$ that produced $r_i$ — at every rung. Once you reach the bottom rung, $r_k = \gcd(a,b)$ , you have a recipe expressing it in terms of $r_{k-2}, r_{k-1}$ . But $r_{k-1}$ itself has a recipe in terms of $r_{k-3}, r_{k-2}$ from the step above, so you substitute that in. This telescopes all the way up the staircase: at each substitution the expression is rewritten purely in terms of remainders one level higher, until only $r_0 = a$ and $r_1 = b$ remain, at which point you have $\gcd(a,b) = ax + by$ for explicit integers $x,y$ . The forward recursion for $(s_i, t_i)$ in the definition is simply this same substitution process performed forward instead of backward — it computes, at each stage $i$ , the coefficients such that $r_i = s_i a + t_i b$ , so that no separate back-substitution pass is even needed.

Figure

The staircase of remainders and the back-substitution path for

a=240,\,b=46

The central theorem

a, b

0 \le r_{i+1} < r_i

(s_k, t_k)

r_2, \dots, r_k

Worked examples

Example 1: $a = 1071$ , $b = 462$ (asymmetric, several steps, negative intermediate coefficients). Run the Euclidean divisions:

1071 = 2\cdot 462 + 147, \qquad 462 = 3\cdot 147 + 21, \qquad 147 = 7 \cdot 21 + 0.

So $r_0 = 1071$ , $r_1 = 462$ , $r_2 = 147$ , $r_3 = 21$ , $r_4 = 0$ ; the gcd is $r_3 = 21$ , with $k = 3$ , $q_1 = 2$ , $q_2 = 3$ , $q_3 = 7$ . Back-substitution. From the second equation, $147 = 462 - 3\cdot 147$ ... rather, isolate the remainder at each step:

21 = 462 - 3\cdot 147.

From the first equation, $147 = 1071 - 2\cdot 462$ . Substitute:

21 = 462 - 3(1071 - 2\cdot 462) = 462 - 3\cdot 1071 + 6\cdot 462 = 7\cdot 462 - 3\cdot 1071.

1071\cdot(-3) + 462\cdot(7) = 21.

Check directly: $1071\cdot(-3) = -3213$ , and $462 \cdot 7 = 3234$ ; indeed $-3213 + 3234 = 21$ . ✓. Forward recursion, as a cross-check. $s_0=1, t_0=0$ ; $s_1=0,t_1=1$ .

s_2 = s_0 - q_1 s_1 = 1 - 2\cdot 0 = 1, \qquad t_2 = t_0 - q_1 t_1 = 0 - 2\cdot 1 = -2.

Check: $s_2 a + t_2 b = 1071 - 2\cdot 462 = 1071 - 924 = 147 = r_2$ . ✓

s_3 = s_1 - q_2 s_2 = 0 - 3\cdot 1 = -3, \qquad t_3 = t_1 - q_2 t_2 = 1 - 3\cdot(-2) = 1+6 = 7.

Check: $s_3 a + t_3 b = -3\cdot 1071 + 7\cdot 462 = -3213 + 3234 = 21 = r_3 = \gcd(1071,462)$ . ✓ — matching the back-substitution answer exactly, as the corollary guarantees.

Example 2: $a = 26$ , $b = 91$ (smaller numbers, $a<b$ , and used to extract a modular inverse afterward). Divisions ( $r_0 = 26, r_1 = 91$ — note the algorithm works regardless of which is larger, since the very first division step $26 = 0\cdot 91 + 26$ would just swap them; to avoid a wasted step, start directly with the larger one on top): Take instead $r_0 = 91, r_1 = 26$ (relabeling so $a=91, b=26$ ; a Bezout pair for $(91,26)$ converts trivially to one for $(26,91)$ by swapping coordinates):

91 = 3\cdot 26 + 13, \qquad 26 = 2\cdot 13 + 0.

So $r_2 = 13 = \gcd(91,26)$ , $k=2$ , $q_1 = 3$ , $q_2 = 2$ . Back-substitution: directly, $13 = 91 - 3\cdot 26$ , so

91\cdot(1) + 26\cdot(-3) = 13.

Check: $91 - 78 = 13$ . ✓. Translating back to the original order $(a,b)=(26,91)$ : $26\cdot(-3) + 91\cdot(1) = 13$ , i.e. the Bezout pair for $(26,91)$ is $(x,y) = (-3,1)$ . Since $\gcd(26,91)=13 \ne 1$ , this does not directly give an inverse; but suppose instead we wanted the inverse of $26$ modulo $99$ (coprime to $26$ ). Then $a=26,\,b=99$ :

99 = 3\cdot 26 + 21, \qquad 26 = 1\cdot 21 + 5, \qquad 21 = 4\cdot 5 + 1, \qquad 5 = 5\cdot 1 + 0.

Here $r_0=99,r_1=26,r_2=21,r_3=5,r_4=1$ , gcd $=1$ , $k=4$ , $q_1=3,q_2=1,q_3=4,q_4=5$ . Back-substitute starting from the last nontrivial remainder:

1 = 21 - 4\cdot 5.

Replace $5 = 26 - 1\cdot 21$ :

1 = 21 - 4(26-21) = 5\cdot 21 - 4\cdot 26.

Replace $21 = 99 - 3\cdot 26$ :

1 = 5(99-3\cdot 26) - 4\cdot 26 = 5\cdot 99 - 15\cdot 26 - 4\cdot 26 = 5\cdot 99 - 19\cdot 26.

So $99\cdot 5 + 26\cdot(-19) = 1$ , giving the Bezout pair $(x,y)=(-19,5)$ for $(a,b)=(26,99)$ , i.e.

26\cdot(-19) \equiv 1 \pmod{99}.

Check: $26\times(-19) = -494$ , and $-494 + 5\times 99 = -494+495 = 1$ . ✓ So $26^{-1} \equiv -19 \equiv 80 \pmod{99}$ ; indeed $26\times 80 = 2080 = 21\times 99 + 1$ . ✓ This is exactly the Modular Inverse computation that the Extended Euclidean Algorithm exists to make routine.

b=0

Scope, edge cases & common traps

Situation	What to do
$a$ or $b$ negative	Run the algorithm on $\|a\|,\|b\|$ , get $(x_0,y_0)$ , then flip sign: if $a<0$ replace $x_0$ by $-x_0$ (and similarly for $b$ ), since $\gcd(a,b)=\gcd(\|a\|,\|b\|)$ .
$b = 0$	Base case: $\gcd(a,0)=a$ (assuming $a>0$ ), Bezout pair $(1,0)$ ; do not enter the division loop.
$a=b=0$	$\gcd(0,0)$ is conventionally $0$ ; the identity $0\cdot x+0\cdot y=0$ holds for all $x,y$ , so Bezout pairs are not unique in the strongest possible sense — this case is usually excluded by hypothesis.
Uniqueness of $(x,y)$	Never unique when $\gcd(a,b)>0$ and $a,b$ are both nonzero: if $(x,y)$ works, so does $(x + n\,b/d,\ y - n\,a/d)$ for any integer $n$ , where $d=\gcd(a,b)$ .
Want smallest positive $x$	Take the algorithm's output $(x,y)$ and reduce $x$ modulo $b/d$ , adjusting $y$ to compensate.

Common trapThe classic error is forgetting that Bezout coefficients are not unique, and asserting "the" solution without pinning down which one

A very common mistake is to compute one Bezout pair $(x_0,y_0)$ via the algorithm and treat it as the answer to "solve $ax+by=\gcd(a,b)$ ," forgetting that the full solution set is

\left(x_0 + n\frac{b}{d},\ y_0 - n\frac{a}{d}\right), \qquad n \in \mathbb{Z}, \quad d = \gcd(a,b),

and that different (equally valid) run orders of the algorithm — e.g. swapping the roles of $a$ and $b$ at the start — can produce a different particular pair from this same family. When computing a modular inverse, this is harmless (any valid $x_0$ works modulo $b$ ), but when the problem demands a specific normalized solution (smallest positive $x$ , or $x,y$ of specific signs), one must explicitly reduce modulo $b/d$ rather than quote the raw algorithm output.

The mathematician behind it

Origins · 1 minEuclid of Alexandria and how this was discovered

Euclid of Alexandria

fl. c. 300 BCE · Ptolemaic Egypt, Hellenistic mathematics

Euclid compiled and systematized geometry and number theory in the Elements, including the algorithm for the greatest common measure of two magnitudes (Book VII, Propositions 1–2), which is the ordinary Euclidean Algorithm in essentially its modern form. The extended version — with explicit integer coefficients rather than just the successive remainders — is not present in Euclid's text; it crystallizes only once Bezout's identity is formulated and one asks for its coefficients constructively. The name "Extended Euclidean Algorithm" is thus a later attribution, honoring the parent procedure while marking a genuinely later addition built directly on top of it.

History

- c. 300 BCE — Euclid's Elements, Book VII, states the algorithm for finding the greatest common measure of two magnitudes.

- 1621 — Bachet de Méziriac publishes a version of the linear Diophantine solvability result in Problèmes plaisants et délectables, an early precursor to explicit coefficient-finding.

- 1624 — Bachet's work already contains, in substance, a method equivalent to back-substitution for two specific numerical cases.

- 1779 — Étienne Bézout publishes general results on the theory of resultants and linear combinations of polynomials, later generalized in naming to the integer identity now called Bezout's Identity.

- 20th century — the "extended" formulation with explicit recursive coefficient sequences

(s_i,t_i)

becomes standard in computational number theory and algorithm design texts, driven by needs in cryptography and computer algebra.

Is the Bezout pair produced by the Extended Euclidean Algorithm unique?

No. If $ax_0+by_0=d=\gcd(a,b)$ , then for any integer $n$ , the pair $\left(x_0+n\frac{b}{d},\ y_0-n\frac{a}{d}\right)$ also satisfies the identity, since the extra terms $n\frac{ab}{d} - n\frac{ab}{d}$ cancel. This produces infinitely many valid Bezout pairs whenever $a,b$ are both nonzero. The algorithm returns one specific pair determined by the exact sequence of quotients encountered; a different but equally valid run (for instance starting the division chain from $(b,a)$ instead of $(a,b)$ ) can produce a different pair from this same infinite family. If a unique "canonical" pair is desired, one typically normalizes by requiring $x$ to lie in a fixed range, such as $0 \le x < b/d$ .

Why not just guess-and-check integer coefficients instead of running the algorithm?

Guessing works for tiny numbers but scales terribly: the search space for $(x,y)$ with $ax+by=d$ has no natural finite bound to search over without already knowing a solution exists and roughly how large it is. The Extended Euclidean Algorithm instead guarantees termination in $O(\log \min(a,b))$ steps — the same bound as the plain Euclidean Algorithm — and produces the coefficients mechanically at each step, with no search at all. For numbers with hundreds of digits, as in cryptographic applications, guess-and-check is computationally infeasible, while the extended algorithm remains fast.

How does this connect to computing a modular inverse?

If $\gcd(a,n)=1$ , running the algorithm on $(a,n)$ yields integers $x,y$ with $ax+ny=1$ . Reducing modulo $n$ kills the $ny$ term, leaving $ax\equiv 1\pmod n$ , so $x \bmod n$ is precisely the multiplicative inverse of $a$ modulo $n$ . This is the standard, most efficient general method for computing modular inverses, and it is exactly what is used in place of, say, Euler's theorem (which would require computing $a^{\varphi(n)-1}\bmod n$ , generally far more expensive).

Does the algorithm work if

a

b

is negative?

Yes, with a small adjustment. Run the algorithm on the absolute values $|a|, |b|$ to get a Bezout pair $(x_0,y_0)$ for $(|a|,|b|)$ , using $\gcd(a,b)=\gcd(|a|,|b|)$ . Then negate the corresponding coefficient: if $a<0$ , replace $x_0$ with $-x_0$ ; if $b<0$ , replace $y_0$ with $-y_0$ . The resulting pair satisfies $ax+by=\gcd(|a|,|b|)$ because negating both the sign of the input and the sign of its coefficient leaves the product unchanged.

What is the relationship between the sequences

s_i,t_i

and continued fractions?

The quotients $q_1,q_2,\dots,q_k$ produced during the Euclidean divisions are exactly the partial quotients of the continued fraction expansion of $a/b$ . The sequences $s_i,t_i$ (up to sign and an index shift) are precisely the numerators and denominators of the convergents of that continued fraction. This is why the Extended Euclidean Algorithm and continued fraction convergents give the same growth-rate and size bounds on the resulting Bezout coefficients, and it is the reason continued fractions provide an alternative computational route to the same coefficients.

Can the algorithm be adapted to polynomials instead of integers?

Yes. Given two polynomials $f(x), g(x)$ over a field, the same division-with-remainder structure holds (using polynomial long division and comparing degrees instead of absolute values), so both the ordinary and extended Euclidean Algorithms carry over essentially verbatim, computing $\gcd(f,g)$ and polynomials $u(x), v(x)$ with $u f + v g = \gcd(f,g)$ . This polynomial version is a standard tool in computer algebra, coding theory (decoding Reed–Solomon codes), and in constructing field extensions via minimal polynomials.

Is there a matrix formulation of the algorithm?

Yes. Each division step corresponds to multiplying the column vector $(r_{i-1}, r_i)^T$ by the matrix $\begin{pmatrix}0 & 1\\ 1 & -q_i\end{pmatrix}$ to get $(r_i,r_{i+1})^T$ . Multiplying all these matrices together in order gives a single $2\times2$ integer matrix with determinant $\pm 1$ that directly encodes the final Bezout coefficients as its entries. This viewpoint makes clear why the coefficients are always integers (the matrices are integer matrices with determinant $\pm1$ , hence so is any product) and connects the algorithm to the group $SL_2(\mathbb{Z})$ .