Bezout's identity

If you have two measuring jugs, one holding a units and one holding b units, you can produce certain amounts by filling and pouring back and forth. The smallest positive amount you can ever measure out is exactly the greatest common divisor of a and b — and Bezout's identity is the precise statement of why.

It says: for any integers a and b, there exist integers x and y such that a x + b y = gcd(a, b). The coefficients x and y are called Bezout coefficients, and you compute them with the extended Euclidean algorithm by tracking the combinations as you run the division steps backward. They are not unique — many pairs work — but the value gcd(a, b) they produce is.

This identity is the theoretical key behind solving linear Diophantine equations and finding inverses in modular arithmetic. In particular, a x + b y can equal 1 precisely when a and b are relatively prime, which is why coprime numbers always have modular inverses. A frequent slip: gcd(a, b) is the smallest positive value of a x + b y, but a x + b y can equal any multiple of the gcd — not every integer.