# Extended Euclidean algorithm

The extended [Euclidean algorithm](https://www.edgepedia.org/euclidean-algorithm) is a modification of the Euclidean algorithm that, in addition to the greatest common divisor of two integers, computes integers s and t satisfying the Bézout identity \( \gcd(a,b) = s \cdot a + t \cdot b \).<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> The coefficients s and t are called the Bézout coefficients, and the algorithm is the standard computational route to them.<sup>[2](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.10%3A_Computing_Coefficients_for_Bezout%27s_Lemma)</sup> Its main practical use is computing [modular multiplicative inverses](https://www.edgepedia.org/modular-multiplicative-inverse), which underlies key steps in cryptography.<sup>[3](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934860)</sup>

| Key fact | Detail |
|---|---|
| Output | \( \gcd(a,b) \) together with integers s, t such that \( \gcd(a,b) = s \cdot a + t \cdot b \)<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> |
| Basis | Bézout's theorem: for positive integers a and b, such integers s and t always exist<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> |
| Worked result | \( \gcd(803,154) = 11 = 5 \cdot 803 - 26 \cdot 154 \)<sup>[2](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.10%3A_Computing_Coefficients_for_Bezout%27s_Lemma)</sup> |
| Inverse use | If \( \gcd(a,m) = 1 \) and \( s \cdot a + t \cdot m = 1 \), then \( s \bmod m \) is the multiplicative inverse of a modulo m<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> |
| Running time | \( O(\log n) \) division steps; the worst case is consecutive Fibonacci numbers<sup>[4](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup> |
| Polynomial form | Over \( R = \mathbf{k}[x] \) for a field \( \mathbf{k} \), the degrees of the Bézout coefficients grow linearly: \( \deg s_i = n_1 - n_{i-1} \) and \( \deg t_i = n_0 - n_{i-1} \)<sup>[5](https://www.csd.uwo.ca/~mmorenom/CS424/Lectures/EuclideanMethods.html/node4.html)</sup> |
| Software | Sage exposes the computation as `xgcd(a,b)`; GMP provides `mpz_gcdext`<sup>[6](https://math-cs.gordon.edu/ntic/ntic2017/section-bezout-id.html)</sup><sup> • </sup><sup>[7](https://gmplib.org/gmp-man-6.2.1.pdf)</sup> |

## What the extension adds

The ordinary Euclidean algorithm computes only the greatest common divisor: it repeatedly replaces the pair \((a, b)\) with \((b, a \bmod b)\) until the remainder is zero, at which point the last nonzero divisor is the gcd.<sup>[3](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934860)</sup> The extension keeps additional bookkeeping during the same steps so that the gcd can also be written as an integer linear combination of the two original numbers.<sup>[8](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)</sup>

The existence of such a combination is the content of [Bézout's theorem](https://www.edgepedia.org/bezouts-theorem): if a and b are positive integers, there exist integers s and t with \( \gcd(a,b) = s \cdot a + t \cdot b \).<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> Because the gcd is usually smaller than both a and b, one of the two coefficients is usually negative.<sup>[8](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)</sup> The representation is not unique.<sup>[6](https://math-cs.gordon.edu/ntic/ntic2017/section-bezout-id.html)</sup>

## How it is computed

**Back-substitution.** One way to obtain the coefficients is to run the standard algorithm while recording each division step, then solve the recorded equations for their remainders and substitute backwards.<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> Each remainder \( r \) from a division step satisfies \( r = n - q \cdot d \), where n is the dividend, q the quotient, and d the divisor, so every remainder can be rewritten in terms of earlier ones.<sup>[8](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)</sup>

The LibreTexts example with a = 803 and b = 154 shows the method. The Euclidean algorithm produces \( 803 = 154 \cdot 5 + 33 \), \( 154 = 33 \cdot 4 + 22 \), \( 33 = 22 \cdot 1 + 11 \), and \( 22 = 11 \cdot 2 + 0 \), so the gcd is 11. Rearranging all but the last equation and substituting backwards gives \( 11 = 5 \cdot 33 - 1 \cdot 154 \), then \( 11 = 5 \cdot 803 - 26 \cdot 154 \), so s = 5 and t = −26.<sup>[2](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.10%3A_Computing_Coefficients_for_Bezout%27s_Lemma)</sup>

**Forward bookkeeping.** The algorithm can instead maintain, at every step, an expression for the current remainder in terms of the original a and b, updating the coefficient pairs as the divisions proceed. In the notation of the UWO lecture notes, each remainder satisfies \( r_i = s_i \cdot a + t_i \cdot b \), with the coefficients updated by the recurrences \( s_k = s_{k-2} - q_k \cdot s_{k-1} \) and \( t_k = t_{k-2} - q_k \cdot t_{k-1} \), where \( q_k \) is the quotient at step k; the final \( s_k \) and \( t_k \) are the Bézout coefficients.<sup>[5](https://www.csd.uwo.ca/~mmorenom/CS424/Lectures/EuclideanMethods.html/node4.html)</sup> A related tabular variant that avoids the backward pass is known as Blankinship's method.<sup>[2](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.10%3A_Computing_Coefficients_for_Bezout%27s_Lemma)</sup>

## Applications

**Modular inverses.** When \( \gcd(a, m) = 1 \), Bézout's theorem gives integers s and t with \( s \cdot a + t \cdot m = 1 \). Reducing modulo m shows that \( s \bmod m \) is the multiplicative inverse of a modulo m, since \( (s \bmod m) \cdot a \equiv 1 \pmod{m} \).<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> These inverses in turn allow modular equations to be solved.<sup>[1](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)</sup> A cryptography text states that finding the multiplicative inverse of b mod a is what the Euclidean algorithm is mostly used for in that field, and that using it this way is sometimes itself called the extended Euclidean algorithm.<sup>[3](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934860)</sup>

**Linear Diophantine equations.** The extension can be used to solve linear Diophantine equations, equations of the form \( s \cdot a + t \cdot b = c \) in integers.<sup>[8](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)</sup>

**Polynomials and fields.** The algorithm extends beyond integers to other Euclidean domains such as polynomial rings. Over \( R = \mathbf{k}[x] \), where \( \mathbf{k} \) is a field, the degrees of the Bézout coefficients grow linearly with the degrees of the inputs, and the coefficients are essentially unique provided their degrees are small enough.<sup>[5](https://www.csd.uwo.ca/~mmorenom/CS424/Lectures/EuclideanMethods.html/node4.html)</sup> [Polynomial](https://www.edgepedia.org/polynomial) versions of the extended Euclidean algorithm are used to compute inverses in finite fields such as \( \mathrm{GF}(2^m) \).<sup>[9](https://arxiv.org/abs/quant-ph/0407095)</sup>

## Efficiency

The worst case occurs for consecutive [Fibonacci](https://www.edgepedia.org/fibonacci) numbers: since \( f_n \bmod f_{n-1} = f_{n-2} \), computing \( \gcd(f_n, f_{n-1}) \) walks back through the entire [Fibonacci sequence](https://www.edgepedia.org/fibonacci-sequence) before terminating.<sup>[4](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup>

The historical analysis of this running time is its own subject. Jeffrey Shallit, a computer scientist at the [University of Waterloo](https://www.edgepedia.org/university-of-waterloo) whose study appeared in *Historia Mathematica* in 1994, records that credit for the first analysis is traditionally assigned to Gabriel Lamé for his 1844 paper, but that Antoine-André-Louis Reynaud gave a weak bound as early as 1811, Émile Léger knew Lamé's basic result in 1837, and Pierre-Joseph-Étienne Finck gave a complete, valid proof along different lines in 1841.<sup>[10](https://www.sciencedirect.com/science/article/pii/S0315086084710317)</sup> [Observation](https://www.edgepedia.org/observation) that consecutive Fibonacci numbers give particularly long running times dates back at least to the 16th century.<sup>[11](https://arxiv.org/abs/1409.0729)</sup>

## History and software

The connection between the Euclidean algorithm and solving remainder problems was seen early: Bachet de Méziriac was, in 1624, the first to connect these methods with the Euclidean algorithm and with Diophantine analysis.<sup>[12](https://www.sciencedirect.com/science/article/pii/S0315086008000670)</sup> D. E. Knuth has remarked that the Euclidean algorithm is "the oldest nontrivial algorithm that has survived to the present day."<sup>[10](https://www.sciencedirect.com/science/article/pii/S0315086084710317)</sup>

[Computer algebra](https://www.edgepedia.org/computer-algebra) systems and libraries expose the extended computation directly. Sage implements it as `xgcd(a,b)`, a name reflecting "eXtended Euclidean algorithm".<sup>[6](https://math-cs.gordon.edu/ntic/ntic2017/section-bezout-id.html)</sup> The GMP library's `mpz_gcdext` sets g to \( \gcd(a,b) \) and s, t to coefficients with \( a \cdot s + b \cdot t = g \), choosing them so that normally \( |s| < |b|/(2g) \) and \( |t| < |a|/(2g) \), which defines s and t uniquely apart from a few exceptional cases.<sup>[7](https://gmplib.org/gmp-man-6.2.1.pdf)</sup>

## References

1. [CSE 311 Lecture 14: Euclidean Algorithm and Modular Equations, University of Washington](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture14.html)
2. [1.10: Computing Coefficients for Bezout's Lemma, Mathematics LibreTexts](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.10%3A_Computing_Coefficients_for_Bezout%27s_Lemma)
3. [Network Security: Private Communication in a Public World, 3rd Edition (NIST copy)](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934860)
4. [SI 335, Unit 3: Number-Theoretic Computations, United States Naval Academy](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)
5. [The Extended Euclidean Algorithm, University of Western Ontario CS 424 lecture notes](https://www.csd.uwo.ca/~mmorenom/CS424/Lectures/EuclideanMethods.html/node4.html)
6. [NTIC: The Bezout Identity, Gordon College](https://math-cs.gordon.edu/ntic/ntic2017/section-bezout-id.html)
7. [GNU MP 6.2.1 Manual, Chapter 5: Integer Functions](https://gmplib.org/gmp-man-6.2.1.pdf)
8. [21-110: The extended Euclidean algorithm, Carnegie Mellon University](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)
9. [Optimized quantum implementation of elliptic curve arithmetic over binary fields, arXiv](https://arxiv.org/abs/quant-ph/0407095)
10. [Jeffrey Shallit (1994). Origins of the analysis of the Euclidean algorithm. Historia Mathematica 21(4), 401–419.](https://www.sciencedirect.com/science/article/pii/S0315086084710317)
11. [A rigorous version of R. P. Brent's model for the binary Euclidean algorithm, arXiv](https://arxiv.org/abs/1409.0729)
12. [Modular arithmetic before C.F. Gauss, Historia Mathematica](https://www.sciencedirect.com/science/article/pii/S0315086008000670)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Divisibility, GCD, and the integers*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license