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.
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.
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 ▸