Bézout's identity states that, for any two integers and that are not both zero, there exist integers and such that
Here is the positive greatest common divisor of and . The integers and are called Bézout coefficients. A foundational result in number theory, the identity connects divisibility with integer linear combinations and provides a constructive basis for solving linear Diophantine equations and finding modular inverses.
Statement and interpretation
Let . Bézout's identity asserts that can be obtained by adding an integer multiple of to an integer multiple of . More strongly, the set of all such combinations is exactly the set of multiples of :
This statement has two parts:
- Every integer combination is divisible by , because divides both and .
- Every multiple of is an integer combination of and , because an identity can be multiplied by any integer.
Consequently, is the least positive integer combination of and .
For example,
whereas
Thus and are Bézout coefficients for and .
The coefficients need not be positive and are not unique. Indeed, restricting both coefficients to nonnegative integers generally makes the identity impossible.
Coprime integers
Two integers are coprime if their greatest common divisor is . Bézout's identity gives the equivalence
The reverse implication follows immediately: any common divisor of and must divide .
If exactly one of is zero, the identity still holds. For example, if and , choose and . Under the convention , the equation also holds trivially for , although the least-positive-combination interpretation no longer applies.
Proof by the least positive combination
Consider
Because and are not both zero, is nonempty. The well-ordering property of the positive integers ensures that it has a least element, say
Divide by :
Then
If , it would be an element of smaller than , contradicting the choice of . Therefore , so . The same argument shows that .
Every common divisor of and divides . Since is itself a positive common divisor, it follows that
This proof establishes existence without first specifying an algorithm for finding the coefficients.
Computation with the extended Euclidean algorithm
The Euclidean algorithm computes the greatest common divisor by repeated division. Its extended form also computes Bézout coefficients, either by back-substitution or by tracking coefficients during the divisions.
For and , the divisions are
The last nonzero remainder is . Back-substitution gives
Hence
A forward implementation maintains representations
Starting from
each division step updates
The coefficient pair attached to the last nonzero remainder gives the required identity, with a sign adjustment if the remainder is negative.
Nonuniqueness and all coefficient pairs
Suppose
Then all integer solutions of are
Substitution shows that these pairs preserve the value of . Conversely, subtracting two solutions gives
Because and are coprime, their divisibility properties force the stated parametrization.
For , this becomes
Thus Bézout coefficients are not intrinsically a single distinguished pair; different computational conventions can return different valid pairs.
Applications
Linear Diophantine equations
A linear Diophantine equation
has an integer solution if and only if
Necessity follows because every common divisor of divides the left-hand side. For sufficiency, write and multiply a Bézout identity by :
All solutions are therefore
Modular inverses
In modular arithmetic, a multiplicative inverse of modulo an integer is an integer satisfying
Such an inverse exists exactly when .
A Bézout identity
immediately supplies the inverse modulo . For example,
shows that is the inverse of modulo .
Coprime cancellation and prime divisibility
If and , then . To see this, multiply by :
Both terms on the left are divisible by .
For a prime number , this yields Euclid's lemma:
This divisibility principle is central to the uniqueness assertion in the fundamental theorem of arithmetic.
Chinese remainder theorem
Bézout coefficients provide an explicit construction for the Chinese remainder theorem. If and
then the simultaneous congruences
are satisfied by
The solution is unique modulo .
Generalizations
More than two integers
For integers , not all zero, there exist integers such that
This follows by repeatedly applying the two-integer identity, using
In particular, the integers collectively have greatest common divisor exactly when an integer combination of them equals . Collective coprimality does not require pairwise coprimality: have greatest common divisor , and
although every pair has a common divisor greater than .
Polynomials over a field
If are polynomials in one variable over a field , and are not both zero, then there exist such that
The greatest common divisor is conventionally normalized to be monic. Polynomial division and the extended Euclidean algorithm establish the identity just as in the integer case.
For example, in ,
so and are relatively prime.
Ideals and Bézout domains
In the language of abstract algebra, the integer identity says
where is the ideal generated by , and consists of the multiples of their greatest common divisor.
The same property holds in every principal ideal domain. More generally, a Bézout domain is an integral domain in which every finitely generated ideal is principal. Every principal ideal domain is a Bézout domain, but the converse need not hold.
The existence of greatest common divisors alone does not guarantee Bézout's identity. In the polynomial ring , the polynomials and have greatest common divisor , but no polynomials satisfy
Evaluating at would give . This distinguishes the one-variable polynomial setting over a field from the multivariable setting.
Naming and historical context
The identity is named after the French mathematician Étienne Bézout, whose work included polynomial forms of the result. Its integer form predates him and is closely connected with the ancient Euclidean algorithm. It is distinct from Bézout's theorem in algebraic geometry, which concerns the intersections of algebraic curves.