Extended Euclidean algorithm

related topics
{math, number, function}

The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y (one of which is typically negative) in Bézout's identity

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b.

Contents

Informal formulation of the algorithm

To illustrate the extension of the Euclid's algorithm, consider the computation of gcd(120, 23), which is shown on the table on the left. Notice that the quotient in each division is recorded as well alongside the remainder.

In this case, the remainder in the fourth line (which is equal to 1) indicates that the gcd is 1; that is, 120 and 23 are coprime (also called relatively prime). For the sake of simplicity, the example chosen is a coprime pair; but the more general case of gcd other than 1 also works similarly.

There are two methods to proceed, both using the division algorithm, which will be discussed separately.

Iterative method

This method computes expressions of the form ri = axi + byi for the remainder in each step i of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:

Full article ▸

related documents
Template (programming)
Taylor's theorem
Cholesky decomposition
Square root
Integer
Hausdorff dimension
Icon (programming language)
Kernel (matrix)
Tail recursion
Metric space
Dirac delta function
Cantor's diagonal argument
Equivalence relation
Set (mathematics)
Vigenère cipher
Standard ML
Operator
Supremum
Interpolation
Complete metric space
Exponential function
Monoid
L'Hôpital's rule
Insertion sort
Semidirect product
PL/SQL
Riemannian manifold
Communication complexity
Category theory
Abstraction (computer science)