Bézout's Identity

(a,b) = ax + by — the gcd as an integer combination.

The idea

Theorem (Bézout's identity).

For any integers $a$ and $b$, not both zero, there are integers $x$ and $y$ with $ax + by = \gcd(a, b).$

The coefficients come from the Euclidean algorithm. Each of its lines has the form (larger) $=$ (quotient)(smaller) $+$ (remainder), so each remainder equals one of the two numbers above it minus a whole multiple of the other. Reading down the chain, every remainder is an integer combination of $a$ and $b$ — in particular the last nonzero remainder, which is the gcd.

Algorithm.

Algorithm: Extended Euclidean Algorithm Input: integers a and b, not both zero Output: g = gcd(a, b) and integers x, y with ax + by = g 1. run the Euclidean algorithm forward, recording each line: (larger) = (quotient)(smaller) + (remainder) // stop at remainder 0; the last nonzero remainder is g 2. solve each recorded line for its remainder: (remainder) = (larger) − (quotient)(smaller) 3. start from the solved line whose remainder is g 4. substitute the solved line directly above for the remainder it mentions; collect like terms // g stays a combination of two consecutive numbers of the chain 5. if the combination uses anything besides a and b, go to step 4, one line up 6. the equation reads ax + by = g; return x and y

The gcd is also the least positive value that $ax + by$ can take, because every common divisor of $a$ and $b$ divides $ax + by$ for every choice of $x$ and $y$. In fact, as $x$ and $y$ range over the integers, the values $ax + by$ are exactly the multiples of $g = \gcd(a, b)$, evenly spaced along the number line.

Reducing the identity modulo $n$ is why coprime numbers have modular inverses: when $\gcd(a, n) = 1$, reading $ax + ny = 1$ modulo $n$ gives $ax \equiv 1 \pmod{n}$, so $x$ is an inverse of $a$.

Ways to work on it

Not sure where to start? Take the ten-question placement test.