Bézout's Identity — Drag u and v to Make ua + vb Land on the GCD

Here is a surprising fact about the integers.

For any two integers a and b (not both zero), there exist integers u and v such that
u a + v b = \gcd(a, b).

This is Bézout's identity. It says the greatest common divisor of a and b can always be written as an integer combination of a and b — you can always weight the two numbers by some integer multipliers (positive, negative, or zero) so the result is exactly their GCD.

Even stronger: the set of values \{ua + vb : u, v \in \mathbb{Z}\} is exactly the set of integer multiples of \gcd(a, b). So \gcd(a, b) is the smallest positive number this expression can produce. Nothing smaller is achievable; every multiple of the GCD is.

The interactive below lets you feel this fact.

Drag to hit the GCD

Pick a = 12 and b = 18. Their GCD is 6 (check: 12 = 2 \times 2 \times 3, 18 = 2 \times 3 \times 3, common part is 2 \times 3 = 6).

Drag the slider below to change u. The readout shows u a + v b for a fixed v = -1. Watch the value step through integers — but notice it only hits multiples of 6. You can never land on 5, 7, or any non-multiple of 6, no matter what integer u you pick.

a = b = v = u = 2:

Interactive exploration of $ua + vb$. With the defaults $a = 12, b = 18, v = -1$, drag $u$ from $-5$ to $+5$. The output hits $-78, -66, -54, -42, -30, -18, -6, 6, 18, 30, 42$ — every value is a multiple of $6$. At $u = 2$, the expression equals $6 = \gcd(12, 18)$, achieving Bézout's identity with $u = 2, v = -1$. Change $a, b, v$ to experiment.

What you are seeing

Bézout's identity is really two facts packaged together.

Fact 1: u a + v b is always a multiple of \gcd(a, b). If d = \gcd(a, b), then d \mid a and d \mid b, so d \mid (u a + v b) for any integers u, v. This is the "divisibility is linear" property.

Why: a = d \cdot k_1 and b = d \cdot k_2, so u a + v b = d(u k_1 + v k_2), a multiple of d.

This fact rules out hitting anything except multiples of d. The slider's readout can never land on 5, 7, 8, 11, 13 because those are not multiples of 6 — the arithmetic simply does not permit it.

Fact 2: \gcd(a, b) itself is achievable as u a + v b for some choice of u, v. This is the surprising half. It is not obvious at all. It says that although the linear combinations u a + v b are constrained to multiples of the GCD, the GCD itself is attainable — there is always at least one pair (u, v) that hits it exactly.

Taken together, Facts 1 and 2 say: the set of values \{u a + v b\} equals the set of integer multiples of \gcd(a, b).

How do you find u and v?

The extended Euclidean algorithm gives you a constructive method. Work through the ordinary Euclidean algorithm (find the GCD), and then back-substitute to express each remainder as a combination of a and b.

Example: find u, v for a = 12, b = 18.

Euclidean algorithm:

18 = 1 \cdot 12 + 6

12 = 2 \cdot 6 + 0

The last non-zero remainder is 6, so \gcd(12, 18) = 6.

Back-substitute. From the first line, 6 = 18 - 1 \cdot 12. That is already our Bézout relation: u = -1, v = 1.

Check: (-1)(12) + (1)(18) = -12 + 18 = 6. \checkmark

Why the back-substitution trick works: at each step of the Euclidean algorithm, the remainder can be written as a linear combination of the two numbers from the previous step. Walking back through the algorithm lets you express the final GCD as a combination of the original a and b.

A longer example: a = 252, b = 105.

252 = 2 \cdot 105 + 42
105 = 2 \cdot 42 + 21
42 = 2 \cdot 21 + 0

\gcd(252, 105) = 21.

Back-substitute:

From line 2: 21 = 105 - 2 \cdot 42.
Substitute 42 = 252 - 2 \cdot 105 from line 1:

21 = 105 - 2(252 - 2 \cdot 105) = 105 - 2 \cdot 252 + 4 \cdot 105 = 5 \cdot 105 - 2 \cdot 252.

So u = -2, v = 5, and (-2)(252) + (5)(105) = -504 + 525 = 21. \checkmark

A second slider: co-prime case

Now let a = 7, b = 11. The GCD is 1 (they share no prime factors). By Bézout, you can write 7u + 11v = 1 for some integers.

Try u = -3 and v = 2: (-3)(7) + (2)(11) = -21 + 22 = 1. \checkmark

u = -3:

With $a = 7, b = 11$ (co-prime), the GCD is $1$. The combination $7u + 11v$ can hit *every* integer — because every integer is a multiple of $1$. At $u = -3, v = 2$, you land exactly on $1$.

When a and b are co-prime, the Bézout combination can reach every integer — not just multiples of some larger number. This fact is crucial for understanding modular arithmetic: u is the multiplicative inverse of a modulo b (and vice versa).

The big picture

Bézout's identity ties together three ideas.

GCD as the finest common "step." The GCD of a and b is the smallest positive "step size" you can build from a and b using integer combinations. Think of a and b as two calipers with fixed widths; Bézout says that by combining them (adding some copies of one, subtracting some copies of the other), you can measure any multiple of the GCD — and nothing smaller.

Linear combinations reveal divisibility. d \mid \gcd(a, b) if and only if d divides every integer combination of a and b. This is the "dual" view of the GCD — characterised not by factorisation, but by how a and b combine.

Constructive content. Unlike prime factorisation, Bézout is algorithmic. You compute the Bézout coefficients from the Euclidean algorithm in time roughly \log(\min(a, b)) — very fast. This is why Bézout appears everywhere in computer arithmetic (cryptography, modular inverse computation, RSA).

A quick proof sketch

You can prove Bézout's identity using the Euclidean algorithm. The argument is essentially "the algorithm itself demonstrates it": every remainder produced by the Euclidean algorithm can be written as a linear combination of a and b, and the last non-zero remainder is \gcd(a, b). Walking back up gives the coefficients.

A more conceptual proof: let S = \{ua + vb : u, v \in \mathbb{Z}\} restricted to positive values. By the well-ordering principle, S has a smallest element, call it d. Show that d \mid a and d \mid b (use the division algorithm: a = qd + r with 0 \leq r < d; if r > 0, then r \in S and r < d, contradicting minimality). So d is a common divisor, hence d \leq \gcd(a, b). But also \gcd(a, b) \mid d (by Fact 1), so \gcd(a, b) \leq d. Hence d = \gcd(a, b), and d \in S — so \gcd(a, b) is achievable. \square

Where Bézout leads next

Bézout's identity is a gateway to modular arithmetic, number-theoretic algorithms, and parts of algebra:

Modular inverse. If \gcd(a, m) = 1, Bézout gives u, v with u a + v m = 1. Modulo m, this reads u a \equiv 1 \pmod m, so u is the inverse of a mod m.
Linear Diophantine equations. "Find integers x, y with a x + b y = c." This has solutions iff \gcd(a, b) \mid c (by Bézout). The solution set is a one-parameter family.
Chinese Remainder Theorem. Bézout's identity is the engine behind constructing simultaneous solutions to systems of modular equations.
Ideals in ring theory. The set \{u a + v b : u, v \in \mathbb{Z}\} is the "ideal generated by a and b." Bézout says this ideal equals the ideal generated by \gcd(a, b), and in \mathbb{Z} every ideal is generated by a single element — the principal ideal domain property.

Each of these is a major topic on its own. Bézout's identity is the thread that runs through them all.

The one-line takeaway

Bézout's identity says \gcd(a, b) is always a linear combination ua + vb of a and b with integer coefficients, and in fact every multiple of \gcd(a, b) is — and nothing else is. The slider shows both facts at once: drag u, and the output lights up only on multiples of the GCD, hitting the GCD exactly at the Bézout coefficients.

The identity packages the GCD as a constructive, computable object — the smallest positive integer combination of a and b — and that packaging unlocks modular arithmetic, cryptography, and classical number theory.