Bezout's Identity

Take two integers, say $252$ and $105$ . Can you always find whole numbers $x$ and $y$ , possibly negative? These numbers should satisfy $252x + 105y$ equals their greatest common divisor. This question looks innocent. But it sits at the foundation of nearly all elementary number theory. It is the precise statement that the greatest common divisor is not just a number you can compute. It is also a number you can build out of the original two integers. This construction uses only addition, subtraction, and integer scaling. Bézout's identity answers this question completely, and does more. It characterizes exactly which integers arise as $252x+105y$ for varying $x,y$ . These are namely all multiples of $\gcd(252,105)=21$ , and nothing else. This dual nature — an existence statement and a classification statement — is what makes the identity so load-bearing. It converts a purely multiplicative notion (divisibility, common divisors) into an additive, linear one (integer combinations). That translation is the single most useful trick in the elementary theory of integers. The identity is the theoretical engine behind the Euclidean Algorithm. Run in reverse, the algorithm's steps produce the coefficients $x,y$ explicitly. This gives the Extended Euclidean Algorithm. It is also the quiet reason Euclid's Lemma holds (if a prime divides a product it divides a factor). It is the reason linear Diophantine equations $ax+by=c$ are solvable exactly when $\gcd(a,b)\mid c$ . And it is the reason modular inverses exist whenever $\gcd(a,n)=1$ . This is the starting point for solving Linear Congruences. This article states and proves Bézout's identity from first principles. It uses only the Well-Ordering Principle and the division algorithm. It proves the full converse characterizing representable integers. It works two concrete asymmetric examples by hand. And it shows exactly which hypothesis cannot be dropped (that $a,b$ are not both zero).

Key takeaways

For integers $a,b$ not both zero, there exist integers $x,y$ with $ax+by=\gcd(a,b)$ .
The set of all values $\{ax+by : x,y \in \mathbb{Z}\}$ equals exactly the set of multiples of $\gcd(a,b)$ .
The coefficients $x,y$ are never unique; the full solution set is an explicit line of lattice points.
Proved via the well-ordering principle: take the smallest positive value of $ax+by$ , show it divides both $a$ and $b$ .
The identity is the theoretical justification for the Extended Euclidean Algorithm and for solvability of $ax+by=c$ .
Key idea: the gcd is the smallest positive integer expressible as an integer linear combination of $a$ and $b$ .

Where this lives today

Bézout's identity is the computational backbone of modular arithmetic in cryptography: the Extended Euclidean Algorithm uses exactly the back-substitution shown above to compute modular inverses, the core operation inside RSA key generation, Diffie–Hellman exchange setup, and elliptic curve cryptography. In coding theory, it underlies the Chinese Remainder Theorem's constructive proof, which reconstructs a number from its residues by explicitly building Bézout coefficients for the moduli. In computer algebra systems, solving linear Diophantine equations $ax+by=c$ is done by first checking $\gcd(a,b)\mid c$ and then scaling a Bézout pair — precisely the argument used in Example 2. In abstract algebra, the identity generalizes verbatim to any Principal Ideal Domain (polynomial rings over a field, Gaussian integers, and more), where it is the statement that every ideal is principal and generated by a gcd; this generalization is one of the first deep structural facts students meet when moving from $\mathbb{Z}$ to ring theory. In numerical analysis and lattice-based cryptography, Bézout-type combinations appear in lattice reduction algorithms (e.g. the LLL algorithm) that search for short integer combinations of basis vectors, a higher-dimensional analogue of exactly this identity.

Ask the tutor: Can you show me step by step how the Extended Euclidean Algorithm recovers a Bézout pair for gcd(1740, 493)?

a,b \in \mathbb{Z}

Intuition

Think of $a$ and $b$ as two step sizes you are allowed to walk, forward or backward, along the number line, and you may combine any number of steps of each kind (that is what "integer multiple" means). The set of all positions you can reach, $S = \{ax+by\}$ , turns out to be beautifully rigid: it is always an evenly spaced grid of points, a copy of $d\mathbb{Z}$ for some $d\ge 0$ . Bézout's identity says this $d$ is precisely $\gcd(a,b)$ — the largest common divisor is also the smallest positive reachable distance. The key structural fact hiding underneath is that $S$ is closed under addition, subtraction, and scaling by any integer — it is what algebraists call an ideal of $\mathbb{Z}$ — and every such subset of $\mathbb{Z}$ that contains a nonzero element is automatically the multiples of its own smallest positive element. This is why the proof does not need to mention the Euclidean Algorithm at all: it is a direct consequence of the Well-Ordering Principle, the fact that every nonempty set of positive integers has a least element.

Figure

Reachable combinations of a=252, b=105 form exactly the multiples of d=21

Prime-power lattice picture

A second way to see the identity is geometrically, through the lattice of pairs $(x,y)$ and the linear map $(x,y)\mapsto ax+by$ .

Figure

Lattice points (x,y) mapped by 252x+105y always hit multiples of 21

Both pictures illustrate the same content: no matter how you combine $252$ and $105$ with integer coefficients, you can never escape the multiples of $21$ , and $21$ itself is achievable, e.g. with $(x,y) = (-2,5)$ : $252(-2) + 105(5) = -504+525 = 21$ .

a, b \in \mathbb{Z}

a,b\in\mathbb{Z}

a,b

S = \{ax+by : x,y\in\mathbb{Z}\}

ax_0+by_0=d=\gcd(a,b)

ax+by = d = ax_0+by_0

Worked examples

Example 1: $a = 462$ , $b = 195$ . Run the Euclidean Algorithm forward to find $d=\gcd(462,195)$ , recording each quotient and remainder:

462 = 2\cdot 195 + 72

195 = 2\cdot 72 + 51

72 = 1\cdot 51 + 21

51 = 2\cdot 21 + 9

21 = 2\cdot 9 + 3

9 = 3\cdot 3 + 0.

The last nonzero remainder is $d = 3$ , so $\gcd(462,195) = 3$ . Now unwind the steps (back-substitution), which is exactly the theorem's proof made algorithmic — the Extended Euclidean Algorithm:

3 = 21 - 2\cdot 9

= 21 - 2(51 - 2\cdot 21) = 5\cdot 21 - 2\cdot 51

= 5(72 - 51) - 2\cdot 51 = 5\cdot 72 - 7\cdot 51

= 5\cdot 72 - 7(195 - 2\cdot 72) = 19\cdot 72 - 7\cdot 195

= 19(462 - 2\cdot 195) - 7\cdot 195 = 19\cdot 462 - 45\cdot 195.

Check: $19 \times 462 = 8778$ , and $45 \times 195 = 8775$ , so $19\cdot 462 - 45\cdot 195 = 8778 - 8775 = 3$ . ✓ So $(x,y) = (19,-45)$ is a Bézout pair: $462(19) + 195(-45) = 3 = \gcd(462,195)$ . By the corollary, every Bézout pair is $\left(19 + 65t,\; -45 - 154t\right)$ for $t\in\mathbb{Z}$ , since $b/d = 195/3=65$ and $a/d=462/3=154$ . Checking $t=-1$ : $(x,y)=(-46,109)$ , and $462(-46)+195(109) = -21252 + 21255 = 3$ . ✓

Example 2: $a = 1001$ , $b = 336$ (asymmetric, testing the characterization half of the theorem). Euclidean algorithm:

1001 = 2\cdot 336 + 329

336 = 1\cdot 329 + 7

329 = 47\cdot 7 + 0.

So $d = \gcd(1001,336) = 7$ . Back-substitute:

7 = 336 - 329

= 336 - (1001 - 2\cdot 336) = 3\cdot 336 - 1001.

Check: $3(336) - 1001 = 1008 - 1001 = 7$ . ✓ So $(x,y) = (-1,3)$ works: $1001(-1)+336(3) = 7$ . Now use the characterization half of the theorem to test membership: is $91$ an integer combination of $1001$ and $336$ ? Since $91 = 13\cdot 7$ is a multiple of $d=7$ , the theorem guarantees yes, and gives an explicit witness by scaling: $91 = 13\cdot 7 = 1001(-13) + 336(39)$ . Verify: $1001\times(-13) = -13013$ , $336\times 39 = 13104$ , sum $= 91$ . ✓ Is $10$ an integer combination of $1001$ and $336$ ? Since $\gcd(1001,336)=7$ and $7 \nmid 10$ , the theorem's characterization ( $S = 7\mathbb{Z}$ ) guarantees this is impossible — no integers $x,y$ satisfy $1001x + 336y = 10$ , regardless of how cleverly chosen. This negative conclusion is exactly the power of the "only multiples of $d$ " half of Bézout's identity: it is not merely an existence result but a complete classification.

a,b

Scope, edge cases & common traps

Situation	What holds	Common mistake
$a,b$ both nonzero	Full theorem applies; unique family of solutions given by corollary	Believing $(x,y)$ is unique
One of $a,b$ is zero, other nonzero	$\gcd(a,0)=\|a\|$ ; identity trivially $a\cdot(\pm1)+0\cdot y = \|a\|$ for any $y$	Forgetting $y$ is unconstrained here
$a,b$ both zero	Theorem hypothesis fails; no genuine content	Silently plugging in $\gcd(0,0)=0$ and claiming a real Bézout pair exists
$a,b$ negative	Theorem still applies verbatim; $\gcd$ always taken positive	Assuming $x,y$ must be positive or that signs of $a,b$ restrict signs of $x,y$
Existence of some solution to $ax+by=c$	Solvable iff $d \mid c$ (direct corollary of characterization)	Assuming solvability whenever $c>0$ , ignoring the divisibility condition

Common trapThe converse trap: existence of a representation does not mean every representation gives the gcd

A frequent error is to find some integers $x,y$ with $ax+by = k$ for a positive $k$ , and conclude $k = \gcd(a,b)$ . This is false in general: for $a=6,b=4$ , the pair $x=1,y=-2$ gives $6(1)+4(-2) = -2$ , and $x=-1,y=2$ gives $2$ , which is $\gcd(6,4)$ — but $x=2,y=1$ gives $16$ , a multiple of the gcd but not equal to it. The theorem guarantees $\gcd(a,b)$ is the smallest positive value achieved, and every achieved positive value is a multiple of it — not that every representation instantly reveals the gcd. Always separately confirm minimality (e.g. via the Euclidean algorithm) before naming a computed value "the gcd."

The mathematician behind it

Origins · 1 minÉtienne Bézout and how this was discovered

ÉB

Étienne Bézout

1730–1783 · France, Ancien Régime mathematics and military examinations

Bézout was a French mathematician best known for his 1779 treatise Théorie générale des équations algébriques, which studied the elimination theory of systems of polynomial equations and established what is now called Bézout's theorem on the intersection number of plane curves. The integer identity that bears his name today is, historically, a special linear case of ideas that trace back further — to Bachet de Méziriac's 1624 work on integer solutions of linear equations, itself building on Euclid's algorithm from antiquity — but Bézout's systematic treatment of resultants and linear combinations of polynomial and integer quantities led his name to be attached to this entire family of results. He served for decades as an examiner of naval and artillery cadets in France, and wrote widely used mathematics textbooks for that purpose, making rigorous computational number theory and algebra part of standard technical education.

History

- 1624: Claude Gaspard Bachet de Méziriac publishes a method for solving linear Diophantine equations

ax+by=c

using the Euclidean algorithm, in Problèmes plaisants et délectables.

- 1730: Étienne Bézout is born in Nemours, France.

- 1764–1779: Bézout develops general elimination theory for systems of polynomial equations, culminating in his theorem on intersection multiplicities of algebraic curves.

- 1783: Bézout dies; his name becomes attached both to the polynomial intersection theorem and, by extension, to the integer linear combination identity.

- 20th century: the identity is formalized as a foundational lemma in the ideal theory of

\mathbb{Z}

and generalized to principal ideal domains and Euclidean domains in abstract algebra.

Is the Bézout pair

(x,y)

unique for given

a,b

No. If $(x_0,y_0)$ is one Bézout pair for $\gcd(a,b)=d$ with $a,b$ both nonzero, then every pair of the form $(x_0 + t\cdot b/d,\ y_0 - t\cdot a/d)$ for $t\in\mathbb{Z}$ is also a Bézout pair, and these are all of them, as proved in the corollary above. Geometrically, the solutions form an infinite arithmetic progression of lattice points along a line of slope $-a/b$ in the $(x,y)$ -plane. Algorithmically, the Extended Euclidean Algorithm returns one specific such pair — typically the one with smallest absolute values — but any valid pair works equally well for applications like computing modular inverses.

Does Bézout's identity require

a

and

b

to be coprime?

No, and this is a common point of confusion. The identity holds for any integers $a,b$ not both zero, producing $ax+by=\gcd(a,b)$ , which need not be $1$ . The special case $\gcd(a,b)=1$ (coprimality) is important enough to deserve its own name, sometimes stated as: $a,b$ are coprime if and only if there exist $x,y$ with $ax+by=1$ . This special case is exactly what powers the proof of Euclid's Lemma and the existence of modular inverses for Linear Congruences, but the general identity applies regardless of whether $a,b$ share a common factor.

How does Bézout's identity relate to solving the general linear Diophantine equation

ax+by=c

It gives a complete solvability criterion and construction method. First, $ax+by=c$ has an integer solution if and only if $d=\gcd(a,b)$ divides $c$ ; this follows immediately from the characterization $\{ax+by\}=d\mathbb{Z}$ . If $d\mid c$ , write $c = d k$ and take any Bézout pair $(x_0,y_0)$ with $ax_0+by_0=d$ ; then $(kx_0, ky_0)$ solves $ax+by=c$ . All solutions then form the arithmetic family described in the corollary, scaled appropriately. This is the standard method used in both hand computation and computer algebra systems.

Why does the proof avoid using the Euclidean Algorithm directly?

To keep the logical foundations clean and non-circular. The proof given here uses only the Well-Ordering Principle and basic divisibility, which makes it independent of, and in fact more fundamental than, the algorithmic machinery of the Euclidean Algorithm. This matters because the Extended Euclidean Algorithm, which computes explicit Bézout coefficients via back-substitution, is best understood as an efficient constructive method for producing the pair $(x,y)$ that the well-ordering proof only asserts exists. Keeping the existence proof separate from the algorithm avoids circular reasoning and clarifies which parts of the theory are purely existential versus computational.

Does an analogous identity hold for more than two integers?

Yes. For integers $a_1,\ldots,a_n$ not all zero, there exist integers $x_1,\ldots,x_n$ with $a_1x_1+\cdots+a_nx_n = \gcd(a_1,\ldots,a_n)$ , and the set of all such combinations equals the multiples of that gcd. The proof is essentially identical: apply the well-ordering principle to the set of positive integer combinations of $a_1,\ldots,a_n$ , show the least positive element divides every $a_i$ and is divisible by every common divisor. In practice one often computes the multi-integer gcd and its Bézout coefficients by repeatedly applying the two-variable case, e.g. $\gcd(a,b,c) = \gcd(\gcd(a,b),c)$ .

What goes wrong if I try to apply Bézout's identity to real numbers instead of integers?

The identity is specifically a statement about the integers $\mathbb{Z}$ , and it fails for real numbers in the relevant sense. For real $a,b$ , the set $\{ax+by : x,y\in\mathbb{R}\}$ is either $\{0\}$ (if $a=b=0$ ) or all of $\mathbb{R}$ (otherwise, since real linear combinations can produce any real number by scaling), so there is no analogue of "smallest positive combination" — the reals are densely ordered with no least positive element, so the well-ordering step of the proof has no foothold. The identity genuinely depends on integers forming a discrete, well-ordered structure; its natural home in abstract algebra is the broader class of Euclidean domains and principal ideal domains, not general fields or rings.

Can Bézout's identity be used to prove Euclid's Lemma, and if so how?

Yes, and this is one of its most important consequences. Euclid's Lemma states that if a prime $p$ divides a product $ab$ , then $p\mid a$ or $p\mid b$ . Suppose $p\nmid a$ ; since $p$ is prime, $\gcd(p,a)=1$ . By Bézout's identity there exist integers $x,y$ with $px+ay=1$ . Multiply both sides by $b$ : $pbx+aby=b$ . Since $p\mid pbx$ trivially and $p \mid ab$ by hypothesis (so $p\mid aby$ ), $p$ divides the sum $pbx+aby=b$ . Hence $p\mid b$ , completing the proof. This derivation is non-circular because Bézout's identity was established independently using only the well-ordering principle.