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:
“Whenever there are in any country uncultivated lands and unemployed poor, it is clear that the laws of property have been so far extended as to violate natural right. The earth is given as a common stock for man to labor and live on.... The small landowners are the most precious part of a state.”
—Thomas Jefferson (1743–1826)