A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Bézout's identity states that for any integers a and b, there exist integers x and y such that ax + by = gcd(a,b). This fundamental result expresses the gcd as a linear combination of a and b, directly connecting divisibility to linear Diophantine equations.
Use the extended Euclidean algorithm to compute gcd(a,b) and simultaneously find the Bézout coefficients x and y. Verify with examples like gcd(35,15) step-by-step.
Thinking the coefficients x and y are unique (infinitely many solutions exist). Assuming x and y must be positive.
You already know from the Euclidean algorithm that gcd(a, b) can be computed by repeatedly applying the division algorithm: divide a by b, take the remainder, and repeat. Bézout's identity says something deeper: that gcd is not just a number you can calculate, but a number you can *express* as a combination of a and b. Specifically, there exist integers x and y — possibly negative — such that ax + by = gcd(a, b). This is the Bézout identity, and it turns the gcd from a divisibility fact into an algebraic object.
The constructive proof comes from running the Euclidean algorithm in reverse. At each step of the algorithm you have an equation like r_{k} = r_{k-2} - q_k · r_{k-1}. Each remainder is a linear combination of the original inputs. By substituting back up the chain of equations — the extended Euclidean algorithm — you eventually express the final nonzero remainder (the gcd) as an integer linear combination of a and b. For example, gcd(35, 15) = 5: the Euclidean algorithm gives 35 = 2·15 + 5, so 5 = 35 − 2·15, meaning x = 1, y = −2. Check: 1·35 + (−2)·15 = 35 − 30 = 5. ✓
The coefficients are not unique. If (x, y) is one solution to ax + by = gcd(a, b), then so is (x + b/d · t, y − a/d · t) for any integer t, where d = gcd(a, b). This infinite family of solutions is a feature: it generates all solutions to linear Diophantine equations, which you'll study next. The key insight is that ax + by = c has an integer solution if and only if gcd(a, b) divides c — and Bézout's identity is exactly what makes the "if" direction work, since you can scale the (x, y) pair for gcd(a, b) to get a pair for any multiple c.
One powerful consequence: if gcd(a, b) = 1 — that is, a and b are coprime — then there exist integers x and y such that ax + by = 1. This means a has a multiplicative inverse modulo b (namely x mod b), and vice versa. This fact underlies modular inverses, the Chinese Remainder Theorem, and RSA cryptography. The abstract structure behind all of this is that in the integers (a principal ideal domain), every ideal is generated by a single element — the gcd — and Bézout's identity is precisely the statement that the ideal {ax + by : x, y ∈ ℤ} equals {d · n : n ∈ ℤ} where d = gcd(a, b).