Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers "a" and "b", also the coefficients of Bézout's identity, which are integers "x" and "y" such that