Pick any two integers you like — even two that look totally unrelated, say 91 and 35. There is nothing obviously shared between them at a glance. And yet, if you're allowed to multiply each one by some whole number (positive or negative) and add the results, you can land exactly on their greatest common divisor — no more, no less. Here, 91 \cdot 2 + 35 \cdot (-5) = 182 - 175 = 7, and indeed \gcd(91, 35) = 7. That combination didn't need to be guessed by luck — a short, mechanical procedure (below) finds multipliers like these for any starting pair. The point stands: some whole-number combination always reaches the gcd, for absolutely any pair of integers, no matter how "unrelated" they seem.

This guarantee is Bézout's identity, named after the 18th-century French mathematician Étienne Bézout. It is one of the load-bearing walls of number theory — everything from solving equations in whole numbers to the mathematics that keeps your online banking secure rests on it.

Why is this surprising at all? Because 91 and 35 share no obvious structure — one isn't a neat multiple of the other, and if you just add or subtract them a few times (91+35=126, 91-35=56, 91-2\cdot35=21, …) the gcd, 7, doesn't jump straight out. It takes exactly the right multipliers to reach it — and Bézout's identity promises those multipliers are always out there waiting to be found, for every pair of integers, without exception.

The statement

Notice what the theorem promises and what it doesn't: it guarantees some pair x, y exists. It says nothing about there being only one such pair, or about the multipliers being tidy, small, or positive — we'll come back to that.

Worked example: finding the coefficients

Take a = 48 and b = 18. First run the Euclidean algorithm forward, dividing at each step:

The last non-zero remainder is 6, so \gcd(48,18)=6. Now walk back up the steps, each time substituting the remainder for what produced it, until only 48 and 18 are left standing:

So x = -1, y = 3. Always check by plugging back in:

This back-substitution trick — running the division steps forward, then unwinding them — is exactly the extended Euclidean algorithm, which the next page turns into a clean, repeatable procedure.

A second example: coefficients can get big

The first example gave nice small coefficients, x=-1, y=3 — don't let that lull you into expecting tidy numbers every time. Try a = 99, b = 78. Forward:

So \gcd(99, 78) = 3. Back-substituting, step by step:

Check: 99 \cdot (-11) + 78 \cdot 14 = -1089 + 1092 = 3. This time the coefficients are two-digit numbers, even though a and b are unremarkable two-digit numbers themselves. In the worst case — proved by Gabriel Lamé in 1844 — the numbers that make the Euclidean algorithm grind through the most steps (and so tend to produce the largest coefficients) are consecutive Fibonacci numbers. Feed the algorithm two neighbouring Fibonacci numbers and you get the slowest possible run for numbers of that size — a lovely, unexpected cameo from one famous sequence inside another.

Existence versus uniqueness

Bézout's identity is an existence statement: it promises a pair (x, y) exists, but it is silent about how many such pairs there are. In fact there are always infinitely many. Once you know one solution (x_0, y_0), every other solution has the form

For our example d = 6, so b/d = 3 and a/d = 8. Starting from (x_0, y_0) = (-1, 3), stepping t = 1 gives (2, -5):

And t = -1 gives (-4, 11), which also works: 48\cdot(-4) + 18\cdot 11 = -192 + 198 = 6. The solutions march off in both directions forever, each one exactly 18 more (or less) in the 48-multiplier's contribution, balanced by 48 less (or more) in the 18-multiplier's — the two shifts always cancel, which is precisely why the sum stays pinned at 6.

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.