# Category:Extended Euclidean algorithm

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

$ax + by = \gcd(a, b). \,$

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.

hijacker
hijacker
hijacker
hijacker

This category currently contains no pages or media.