# Category:Extended Euclidean algorithm

From LiteratePrograms

The **extended Euclidean algorithm** is an algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers *a* and *b*, as well as integers *x* and *y* such that

The algorithm is essentially the same as the Euclidean algorithm, but keeps track of the quotient during the computation in order to find *x* and *y* as above.

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

*This category currently contains no pages or media.*