More than the gcd
The ordinary Euclidean algorithm returns the greatest common divisor of a and b. The extended version also finds integers x and y satisfying the identity a times x plus b times y equals the gcd. This is called Bezout's identity, and those coefficients are extremely useful.
How the coefficients arise
Run Euclid as usual but carry the coefficients along. At the base case, when b reaches zero, the gcd is a, expressed as one times a plus zero times b. As the recursion unwinds, each step rewrites the coefficients using the quotient from that division. Every level produces a fresh pair of x and y that still satisfies Bezout's identity for the numbers at that level.
Why it matters
- It computes the modular inverse: when a and m are coprime, the coefficient x is the inverse of a modulo m.
- That inverse powers modular division, the RSA cryptosystem key setup, and the Chinese remainder theorem.
- It solves linear Diophantine equations, deciding when integer solutions exist.
The cost is the same as plain Euclid, since it only adds a little bookkeeping per step.
Key idea
The extended algorithm tracks Bezout coefficients so the gcd is written as a times x plus b times y; this yields modular inverses, which underpin modular division and cryptography.