Here is a fact that seems almost too good to be true. The greatest common divisor of two numbers can always be written as a combination of them — added and subtracted with whole-number multipliers. This is Bézout's identity, and it is the bridge between divisibility and almost everything that follows.

The statement

The multipliers x, y are called Bézout coefficients. They are not unique — but that the gcd is reachable at all is the powerful part.

An example

We saw \gcd(48, 18) = 6. Bézout promises whole numbers x, y with 48x + 18y = 6, and indeed:

Notice one multiplier is negative — that is essential. Restricted to non-negative multipliers you could never reach a number smaller than both. Allowing subtraction is what lets the combination drop all the way down to the gcd.

Why the smallest positive value is the gcd

Let d be the smallest positive number of the form ax + by. Two short arguments pin it down:

• The gcd divides d. Since \gcd(a,b) divides both a and b, it divides any combination ax + by — so it divides d.
• d divides both a and b. Divide a by d: the remainder a - dq is also of the form a x' + b y', yet it is smaller than d. The only escape is that it equals 0, so d \mid a (and likewise d \mid b).

So d is a common divisor that the gcd divides — which forces d = \gcd(a,b).

The coprime case — a workhorse

When a and b are coprime, Bézout reads:

This single line is the engine behind modular inverses, the Chinese Remainder Theorem, and the correctness of RSA. The next page turns the Euclidean algorithm into a machine that actually computes the coefficients x and y.