The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y (one of which is typically negative) that satisfy Bézout's identity
The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the multiplicative inverse of a modulo b, and y is the multiplicative inverse of b modulo a.
Read more about Extended Euclidean Algorithm: Informal Formulation of The Algorithm, Computing A Multiplicative Inverse in A Finite Field, The Case of More Than Two Numbers
Famous quotes containing the word extended:
“All the Valley quivered one extended motion, wind
undulating on mossy hills”
—Allen Ginsberg (b. 1926)