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:
“I have been accustomed to make excursions to the ponds within ten miles of Concord, but latterly I have extended my excursions to the seashore.”
—Henry David Thoreau (1817–1862)