Extended Euclidean Algorithm

The extended Euclidean algorithm computes, alongside the greatest common divisor of two integers a and b as the ordinary Euclidean algorithm does, a pair of integer coefficients x and y such that a times x plus b times y equals that greatest common divisor, by tracking the sequence of quotients and remainders produced during the standard algorithm's division steps and unwinding them. This coefficient pair, known as Bezout's identity, is central to computing modular multiplicative inverses, needed throughout number-theoretic cryptography including RSA key generation. The technique traces back to the ancient Euclidean algorithm itself, with its extended coefficient-tracking form developed in later number theory.