In Arithmetic and Cryptography & Cryptanalysis, the Extended Euclidean Algorithm is an extension to the Euclidean algorithm. It computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout’s identity, which are integers x and y such that
ax + by = gcd(a,b)
This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. And with the greatest common divisor, it allows one to compute, with almost no extra cost, the quotients of a and b.