Fact-checked by Grok 2 weeks ago

Bézout's identity

Bézout's identity is a in elementary stating that for any integers a and b, not both zero, there exist integers x and y such that ax + by = \gcd(a, b). This result, also called Bézout's lemma, provides a constructive way to express the of a and b as an integer of the two numbers. Although named after the French mathematician (1730–1783), who generalized the identity to polynomials in his 1779 work Théorie générale des équations algébriques, the core idea for integers was first presented by Claude-Gaspard Bachet de Méziriac in 1624. The identity traces its conceptual roots even further to Euclid's Elements (circa 300 BCE), where the Euclidean algorithm implicitly demonstrates the existence of such coefficients through repeated division. A standard proof uses the , which back-substitutes the steps of the to explicitly find the coefficients x and y. The theorem is pivotal in , as it underpins the solution of linear Diophantine equations: ax + by = c has integer solutions \gcd(a, b) divides c. It also characterizes —those with \gcd(a, b) = 1—since such pairs admit coefficients satisfying ax + by = 1, enabling the construction of modular inverses in and beyond. Furthermore, Bézout's identity proves key results like (if a prime p divides ab and \gcd(p, a) = 1, then p divides b) and the structure of the generated by a and b in the , where linear combinations form all multiples of \gcd(a, b). These applications extend to generalizations in domains, such as polynomials over fields, highlighting its broad influence in algebra and .

Statement and Interpretation

Formal Statement for Integers

Bézout's identity, in the context of integers, asserts that for any integers a and b, not both zero, there exist integers x and y such that ax + by = d, where d = \gcd(a, b) is the of a and b. The conditions require a and b to be integers, with at least one nonzero, and d defined as the largest positive integer that divides both a and b. By convention, d is taken to be positive, ensuring uniqueness up to sign in its , though the standard definition fixes it as nonnegative. In the more general linear ax + by = c for an constant c, solutions x and y exist d = \gcd(a, b) divides c. While d is unique under the positive convention, the solutions x and y are not unique; there are infinitely many pairs satisfying the equation, differing by multiples related to a/d and b/d.

Geometric and Algebraic Interpretation

Bézout's identity provides an algebraic interpretation through the lens of ideals in the ring of integers \mathbb{Z}. The set of all integer linear combinations of a and b, denoted \{ax + by \mid x, y \in \mathbb{Z}\}, forms an ideal in \mathbb{Z} that contains both a and b. This ideal is principal and generated by the greatest common divisor d = \gcd(a, b), meaning (a, b) = (d), and d is the smallest positive element in this ideal. In terms of divisibility, Bézout's identity underscores that d divides both a and b, and every common of a and b divides d. The identity demonstrates that d itself is attainable as an linear combination, confirming d as the generator of the ideal and bridging the notions of common divisors and linear expressibility. The identity directly connects to the solvability of linear Diophantine equations of the form ax + by = c. solutions exist d divides c, since any solution must yield a multiple of d, and scaling the coefficients from the identity provides a particular solution when this condition holds. This perspective on linear combinations traces back to early , where expressing common measures as combinations of lengths laid foundational ideas for modern algebraic structures.

Particular and General Solutions

Finding a Particular Solution

To find a particular pair of integers x and y satisfying Bézout's identity ax + by = d, where d = \gcd(a, b), the provides a constructive method by extending the standard to track linear combinations during the computation of the gcd. This approach uses the quotients from the division steps to enable back-substitution, expressing d explicitly as sa + tb for integers s and t. The algorithmic steps are as follows:
  1. Apply the to a and b (assuming a > b > 0 ), generating a sequence of equations: \begin{align*} a &= q_1 b + r_1, \\ b &= q_2 r_1 + r_2, \\ r_1 &= q_3 r_2 + r_3, \\ &\vdots \\ r_{k-2} &= q_k r_{k-1} + r_k, \\ r_{k-1} &= q_{k+1} r_k + 0, \end{align*} where r_k = d is the last non-zero .
  2. Starting from r_k = d, use back-substitution to rewrite each as a linear combination of previous remainders, ultimately in terms of a and b. Each step rearranges the equation r_{i} = r_{i-2} - q_i r_{i-1} and substitutes prior expressions.
This process yields particular coefficients s and t such that d = s a + t b. For illustration, consider a = 48 and b = 18: \begin{align*} 48 &= 2 \cdot 18 + 12, \\ 18 &= 1 \cdot 12 + 6, \\ 12 &= 2 \cdot 6 + 0. \end{align*} Here, d = 6. Back-substituting: $6 = 18 - 1 \cdot 12, and substituting $12 = 48 - 2 \cdot 18: $6 = 18 - 1 \cdot (48 - 2 \cdot 18) = 18 - 48 + 2 \cdot 18 = 3 \cdot 18 - 1 \cdot 48. Thus, a particular solution is x = -1, y = 3, verifying $48(-1) + 18(3) = 6. The is efficient for practical computation, even with large integers, as its is O(\log \min(|a|, |b|)), which scales polynomially with the of the inputs.

Structure of the General Solution

Once a particular solution (x_0, y_0) to the equation ax + by = d is known, where d = \gcd(a, b), the complete set of all solutions can be parameterized as x = x_0 + \frac{b}{d} t, \quad y = y_0 - \frac{a}{d} t for any t \in \mathbb{Z}. This parametric form arises by adding the general solution to the associated homogeneous equation ax + by = 0 to the particular solution. The solutions to the homogeneous equation are of the form x = \frac{b}{d} k, y = -\frac{a}{d} k for k, since substituting yields a \left( \frac{b}{d} k \right) + b \left( -\frac{a}{d} k \right) = \frac{abk}{d} - \frac{abk}{d} = 0. The resulting family of solutions is infinite, with solutions spaced apart by the increments \frac{b}{d} in x and -\frac{a}{d} in y. Moreover, since \gcd\left( \frac{a}{d}, \frac{b}{d} \right) = 1, these increments form a basis for the solution lattice, ensuring that every integer solution is captured uniquely by varying t. To verify, substitute the parametric form into the original equation: a \left( x_0 + \frac{b}{d} t \right) + b \left( y_0 - \frac{a}{d} t \right) = ax_0 + a \frac{b}{d} t + by_0 - b \frac{a}{d} t = (ax_0 + by_0) + \frac{ab}{d} t - \frac{ab}{d} t = d, which holds for any integer t.

Proofs of Existence

Proof Using the Euclidean Algorithm

Bézout's identity states that for any integers a and b, not both zero, there exist integers x and y such that \gcd(a, b) = ax + by. A of this identity follows from the , which not only computes the but also yields the coefficients x and y through an inductive process on the remainders generated by the algorithm. The proof proceeds by on the value of b, assuming that a \geq b > 0. For the base case, if b = [0](/page/0), then \gcd(a, 0) = |a|, and the identity holds with x = 1 and y = [0](/page/0), since a \cdot 1 + 0 \cdot [0](/page/0) = a. This establishes the trivial when the second input is zero. In the inductive step, assume the identity holds for all pairs where the second argument is less than b. Apply the division to write a = qb + r with $0 \leq r < b and quotient q. Then \gcd(a, b) = \gcd(b, r). By the induction hypothesis, there exist integers x' and y' such that \gcd(b, r) = b x' + r y' = d. Substitute r = a - qb into this equation to obtain d = b x' + (a - qb) y' = a y' + b (x' - q y'). Thus, the coefficients for the original pair are x = y' and y = x' - q y', proving the identity holds for (a, b). This back-substitution process is repeated recursively through each step of the Euclidean until the base case is reached, explicitly constructing x and y. The algorithm terminates because each remainder strictly decreases (r < b) and remainders are non-negative integers, which are well-ordered under the usual ordering; the process must eventually reach a remainder of zero. This guarantees that the induction applies and the coefficients are finite integers.

Proof Using Well-Ordering Principle

To prove Bézout's identity using the well-ordering principle, assume without loss of generality that a and b are positive integers (the general case follows by considering absolute values and signs). Consider the set S = \{ |a x + b y| \mid x, y \in \mathbb{Z}, |a x + b y| > 0 \}, which consists of all positive integer linear combinations of a and b. The set S is nonempty, as it contains a (take x=1, y=0) and b. By the , every nonempty of the positive integers has a least , so S has a minimal d > 0. Thus, there exist integers x_0 and y_0 such that d = |a x_0 + b y_0|. To show that d = \gcd(a, b), first prove that d divides both a and b. Apply the division algorithm to a: write a = q d + r where $0 \leq r < d and q \in \mathbb{Z}. Then r = a - q d = a - q |a x_0 + b y_0|. If r > 0, then r can be expressed as a positive linear combination of a and b (adjusting signs appropriately), so r \in S. But r < d contradicts the minimality of d, so r = 0 and d \mid a. Similarly, d \mid b. Next, let e be any common divisor of a and b, so e \mid a and e \mid b. Then e divides any linear combination of a and b, including a x_0 + b y_0, so e \mid d. Thus, d is a common of a and b that is at least as large as any other common , meaning d = \gcd(a, b). By the minimality of d in S, there exist integers x and y such that a x + b y = \gcd(a, b) (or -\gcd(a, b), but the sign can be adjusted). This nonconstructive proof establishes the existence of the integers x and y without providing a method to compute them, unlike the Euclidean algorithm.

Examples and Applications

Diophantine Equation Example

To illustrate Bézout's identity in the context of linear Diophantine equations, consider the equation $15x + 25y = 5, where x and y are integers. First, compute \gcd(15, 25) = 5 using the Euclidean algorithm: $25 = 1 \cdot 15 + 10, $15 = 1 \cdot 10 + 5, $10 = 2 \cdot 5 + 0. Since 5 divides 5, integer solutions exist by Bézout's identity. A particular solution can be found using the by back-substituting: $5 = 15 - 1 \cdot 10, and substituting $10 = 25 - 1 \cdot 15 yields $5 = 15 - 1 \cdot (25 - 1 \cdot 15) = 2 \cdot 15 - 1 \cdot 25. Thus, x = 2, y = -1 is a particular solution, as $15 \cdot 2 + 25 \cdot (-1) = 30 - 25 = 5. The general solution follows the structure given by Bézout's identity: x = 2 + \frac{25}{5}t = 2 + 5t, y = -1 - \frac{15}{5}t = -1 - 3t, where t is any . For verification, substitute t = 0: $15 \cdot 2 + 25 \cdot (-1) = 5; for t = 1: $15 \cdot 7 + 25 \cdot (-4) = 105 - 100 = 5.

Application in Number Theory

Bézout's identity provides a foundational tool for establishing the existence of multiplicative inverses in . Specifically, if \gcd(a, n) = 1, then there exist integers x and y such that a x + n y = 1. Reducing this modulo n yields a x \equiv 1 \pmod{n}, demonstrating that x serves as the modular of a modulo n. This result is crucial for operations in the of integers modulo n. The identity underpins the coprimality conditions essential to , which states that if \gcd(a, m) = 1, then a^{\phi(m)} \equiv 1 \pmod{m}, where \phi is . By ensuring the existence of integers s and t such that s a + t m = 1, Bézout's identity facilitates the manipulation of congruences in proofs involving the structure of \mathbb{Z}/m\mathbb{Z}^\times, enabling the reduction of exponents modulo \phi(m). This connection highlights its role in generalizing to composite moduli. Bézout coefficients also emerge naturally in the theory of s, where they relate to the convergents of the continued fraction expansion of a a/b. For a and b, the convergents p_n/q_n satisfy a q_{n-1} - b p_{n-1} = (-1)^{n-1}, providing explicit Bézout coefficients s = q_{n-1} and t = -p_{n-1} for the equation a s + b t = 1. These coefficients identify the best rational approximations, linking Diophantine approximations to linear combinations in . In cryptography, Bézout's identity supports key generation in the RSA algorithm by enabling the extended Euclidean algorithm to compute the private exponent as the modular inverse of the public exponent modulo \phi(n), after verifying their coprimality via the gcd, ensuring secure modular exponentiation.

Generalizations

To Polynomials over Fields

Bézout's identity generalizes directly to the polynomial ring K, where K is a field. For nonzero polynomials f, g \in K, let d = \gcd(f, g) denote the monic greatest common divisor (unique up to scalar multiples in K^\times, normalized to be monic). There exist polynomials u, v \in K such that uf + vg = d. This expresses the principal ideal generated by f and g as (d), reflecting that K is a principal ideal domain. The proof proceeds via the Euclidean algorithm, mirroring its use for integers but leveraging the division algorithm in K. Assume without loss of generality that \deg f \geq \deg g. Divide f by g to obtain f = q_1 g + r_1 with \deg r_1 < \deg g. Repeat with g and r_1, yielding g = q_2 r_1 + r_2, and continue until a remainder r_k = 0, where r_{k-1} = d (up to scaling to monic). Back-substituting expresses each remainder as a linear combination of f and g, ultimately yielding d = u f + v g. The coefficients u and v produced this way satisfy degree bounds: \deg u < \deg g and \deg v < \deg f when d = 1, with analogous adjustments for general d ensuring minimal-degree solutions where \deg u \leq \deg(g/d) - 1 and \deg v \leq \deg(f/d) - 1. As an illustration over K = \mathbb{Q}, take f(x) = x^2 - 5x + 6 and g(x) = x^2 - 3x + 2. Factoring gives f(x) = (x-2)(x-3) and g(x) = (x-1)(x-2), so d(x) = x - 2. Applying the : f(x) - g(x) = -2x + 4 = -2(x-2), hence x - 2 = -\frac{1}{2} f(x) + \frac{1}{2} g(x), with u(x) = -\frac{1}{2} (constant, degree 0) and v(x) = \frac{1}{2} (constant, degree 0), satisfying the degree bounds relative to \deg(f/d) = 1 and \deg(g/d) = 1.

To Principal Ideal Domains

In a principal ideal domain R, every ideal is principal by definition, and thus for any elements a, b \in R, the ideal they generate, denoted (a, b), is principal, say (a, b) = (d) for some d \in R. Moreover, there exist coefficients x, y \in R such that ax + by = d, where d is a greatest common divisor of a and b in the sense that it generates the ideal (a, b). This directly generalizes Bézout's identity from the integers to arbitrary principal ideal domains. More broadly, an R is called a Bézout domain if every finitely generated of R is principal. This condition is equivalent to the property that for every pair a, b \in R, the (a, b) is principal, generated by some d = ax + by with x, y \in R, thereby extending Bézout's identity to all two-generated . Every is a Bézout domain, since all (finitely generated or otherwise) are principal. However, the converse does not hold without additional structure. A precise characterization states that an R is a if and only if it is a Bézout domain and satisfies the ascending chain condition on principal ideals (ACCP), meaning that every ascending chain of principal ideals stabilizes. This condition ensures that every ideal is finitely generated, and combined with the Bézout property, forces all such ideals to be principal. For instance, the polynomial case over fields, as discussed previously, exemplifies this in the ring k. Examples of principal ideal domains, and thus Bézout domains, include the ring of integers \mathbb{Z} and the polynomial ring k in one indeterminate over a field k. The ring of Gaussian integers \mathbb{Z} = \{ a + bi \mid a, b \in \mathbb{Z} \} is another, as it is a Euclidean domain with respect to the norm N(a + bi) = a^2 + b^2, implying it is a PID. Not all integral domains are Bézout domains. For example, the polynomial ring \mathbb{Z} in one indeterminate over \mathbb{Z} is an integral domain but not Bézout, since the ideal (2, x) is not principal: any single generator would have to divide both 2 and x, but no such nonzero element exists in \mathbb{Z}.

Historical Context

Origins in Diophantine Equations

The origins of Bézout's identity can be traced to ancient efforts in solving linear Diophantine equations of the form ax + by = c, where a, b, x, y, and c are integers, particularly when a and b are coprime. In 7th-century India, Brahmagupta provided the first general solution to such equations in his treatise Brahmasphuṭasiddhānta (Chapter 18), demonstrating how to find integer solutions x and y when \gcd(a, b) = 1 divides c, using methods that effectively express the gcd as a linear combination. Earlier, in 3rd- to 5th-century China, the Sunzi Suanjing addressed related problems through the Chinese Remainder Theorem, solving systems of linear congruences equivalent to linear Diophantine equations modulo coprime moduli, such as finding a number satisfying remainders when divided by 3, 5, and 7. A foundational precursor appeared in around 300 BCE with Euclid's Elements (Book VII, Proposition 2), which describes an algorithm for finding the (gcd) of two integers using repeated subtraction or division, implicitly showing that the gcd divides any of the numbers, though without explicitly constructing the coefficients. This laid the groundwork for proving the existence of integer solutions to linear Diophantine equations when the gcd condition holds. Medieval developments built on these ideas. In 1202, the Italian mathematician (Leonardo of ) discussed coprimality and solutions to linear Diophantine equations in his , including the for gcd computation and problems reducible to equations like ax + by = c, adapting earlier Arabic and Indian methods to European contexts. Concurrently, 10th-11th century Arab mathematicians like al-Karaji extended Diophantine analysis in works such as Al-Fakhri fi'l-jabr wa'l-muqabala, addressing linear equations alongside higher-degree indeterminates and emphasizing integer solutions through algebraic techniques. By the 17th century, European mathematicians recognized the general form of linear combinations in , reviving Diophantine problems through figures like , who explored integer solutions to equations and their connections to gcd properties in correspondence and unpublished notes, bridging ancient methods toward a more systematic theory.

Attribution and Development

(1730–1783), a mathematician renowned for his contributions to elimination theory, generalized the linear combination property to polynomials in his 1779 treatise Théorie générale des équations algébriques. There, he established that the resultant of a has degree equal to the product of the individual degrees, laying foundational work for what became known as in . Although did not originate the identity for integers, his polynomial extension elevated its visibility in 18th-century mathematics, influencing subsequent algebraic developments. Earlier European mathematicians had already articulated the integer case. Claude-Gaspard Bachet de Méziriac presented the core idea for in 1624, stating that if the greatest common divisor of a and b is 1, then integers x and y exist such that ax + by = 1. By 1801, extensively employed the extended form of the identity in his to solve Diophantine equations and develop , crediting predecessors like Bachet without attributing it to Bézout. The naming "Bézout's identity" emerged as a convention in 19th- and 20th-century texts, despite its earlier roots, likely due to Bézout's prominent generalization; it is alternatively termed "Bézout's lemma." This attribution gained traction through influential works, including the 1949 Bourbaki Algèbre, though some historians argue it miscredits Bézout over ancient and precursors. A 2024 analysis further contends that the term is a misnomer, emphasizing origins from onward and critiquing its popularization by Bourbaki. In the late 19th century, integrated Bézout's polynomial theorem into during the 1890s, using it to bound intersection multiplicities and advance . By the 1930s, and her school embedded the identity within abstract , generalizing it to domains as a of modern .