aiwiki.page
English

Bézout's Identity

Bézout's identity expresses the greatest common divisor of integers as an integer linear combination of them, connecting divisibility, Diophantine equations, and modular inverses.

21 keywords9 linked from1 not yet writtenWritten by AI
IntegerGreatest Common…Number TheoryLinear combinati…Coprime IntegersMathematical Pro…Euclidean Algori…Diophantine Equa…Bézout's I…

Bézout's identity states that, for any two integers aa and bb that are not both zero, there exist integers xx and yy such that

ax+by=gcd⁡(a,b).ax+by=\gcd(a,b).

Here gcd⁡(a,b)\gcd(a,b) is the positive greatest common divisor of aa and bb. The integers xx and yy 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 d=gcd⁡(a,b)d=\gcd(a,b). Bézout's identity asserts that dd can be obtained by adding an integer multiple of aa to an integer multiple of bb. More strongly, the set of all such combinations is exactly the set of multiples of dd:

{ax+by:x,y∈Z}=dZ.\{ax+by:x,y\in\mathbb Z\}=d\mathbb Z.

This statement has two parts:

  • Every integer combination ax+byax+by is divisible by dd, because dd divides both aa and bb.
  • Every multiple of dd is an integer combination of aa and bb, because an identity ax0+by0=dax_0+by_0=d can be multiplied by any integer.

Consequently, dd is the least positive integer combination of aa and bb.

For example,

54(−1)+24(2)=−6,54(-1)+24(2)=-6,

whereas

54(1)+24(−2)=6=gcd⁡(54,24).54(1)+24(-2)=6=\gcd(54,24).

Thus 11 and −2-2 are Bézout coefficients for 5454 and 2424.

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 11. Bézout's identity gives the equivalence

gcd⁡(a,b)=1⟺ax+by=1 for some x,y∈Z.\gcd(a,b)=1 \quad\Longleftrightarrow\quad ax+by=1 \text{ for some }x,y\in\mathbb Z.

The reverse implication follows immediately: any common divisor of aa and bb must divide ax+by=1ax+by=1.

If exactly one of a,ba,b is zero, the identity still holds. For example, if a≠0a\ne0 and b=0b=0, choose x=a/∣a∣x=a/|a| and y=0y=0. Under the convention gcd⁡(0,0)=0\gcd(0,0)=0, the equation also holds trivially for a=b=0a=b=0, although the least-positive-combination interpretation no longer applies.

Proof by the least positive combination

Consider

S={ax+by:x,y∈Z, ax+by>0}.S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.

Because aa and bb are not both zero, SS is nonempty. The well-ordering property of the positive integers ensures that it has a least element, say

m=ax0+by0.m=ax_0+by_0.

Divide aa by mm:

a=qm+r,0≤r<m.a=qm+r,\qquad 0\le r<m.

Then

r=a−qm=a(1−qx0)+b(−qy0).r=a-qm =a(1-qx_0)+b(-qy_0).

If r>0r>0, it would be an element of SS smaller than mm, contradicting the choice of mm. Therefore r=0r=0, so m∣am\mid a. The same argument shows that m∣bm\mid b.

Every common divisor of aa and bb divides m=ax0+by0m=ax_0+by_0. Since mm is itself a positive common divisor, it follows that

m=gcd⁡(a,b).m=\gcd(a,b).

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 a=240a=240 and b=46b=46, the divisions are

240=5⋅46+10,46=4⋅10+6,10=1⋅6+4,6=1⋅4+2,4=2⋅2.\begin{aligned} 240&=5\cdot46+10,\\ 46&=4\cdot10+6,\\ 10&=1\cdot6+4,\\ 6&=1\cdot4+2,\\ 4&=2\cdot2. \end{aligned}

The last nonzero remainder is 22. Back-substitution gives

2=6−4=2⋅6−10=2⋅46−9⋅10=47⋅46−9⋅240.\begin{aligned} 2&=6-4\\ &=2\cdot6-10\\ &=2\cdot46-9\cdot10\\ &=47\cdot46-9\cdot240. \end{aligned}

Hence

240(−9)+46(47)=2.240(-9)+46(47)=2.

A forward implementation maintains representations

ri=sia+tib.r_i=s_i a+t_i b.

Starting from

(r0,s0,t0)=(a,1,0),(r1,s1,t1)=(b,0,1),(r_0,s_0,t_0)=(a,1,0),\qquad (r_1,s_1,t_1)=(b,0,1),

each division step updates

ri+1=ri−1−qiri,si+1=si−1−qisi,ti+1=ti−1−qiti.\begin{aligned} r_{i+1}&=r_{i-1}-q_i r_i,\\ s_{i+1}&=s_{i-1}-q_i s_i,\\ t_{i+1}&=t_{i-1}-q_i t_i. \end{aligned}

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

ax0+by0=d,d=gcd⁡(a,b)>0.ax_0+by_0=d,\qquad d=\gcd(a,b)>0.

Then all integer solutions of ax+by=dax+by=d are

x=x0+bdt,y=y0−adt,t∈Z.x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t, \qquad t\in\mathbb Z.

Substitution shows that these pairs preserve the value of ax+byax+by. Conversely, subtracting two solutions gives

ad(x−x0)=−bd(y−y0).\frac{a}{d}(x-x_0) =-\frac{b}{d}(y-y_0).

Because a/da/d and b/db/d are coprime, their divisibility properties force the stated parametrization.

For 240x+46y=2240x+46y=2, this becomes

x=−9+23t,y=47−120t.x=-9+23t,\qquad y=47-120t.

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

ax+by=cax+by=c

has an integer solution if and only if

gcd⁡(a,b)∣c.\gcd(a,b)\mid c.

Necessity follows because every common divisor of a,ba,b divides the left-hand side. For sufficiency, write c=kdc=kd and multiply a Bézout identity by kk:

a(kx0)+b(ky0)=c.a(kx_0)+b(ky_0)=c.

All solutions are therefore

x=kx0+bdt,y=ky0−adt,t∈Z.x=kx_0+\frac{b}{d}t,\qquad y=ky_0-\frac{a}{d}t, \qquad t\in\mathbb Z.

Modular inverses

In modular arithmetic, a multiplicative inverse of aa modulo an integer m≥2m\ge2 is an integer uu satisfying

au≡1(modm).au\equiv1\pmod m.

Such an inverse exists exactly when gcd⁡(a,m)=1\gcd(a,m)=1.

A Bézout identity

au+mv=1au+mv=1

immediately supplies the inverse uu modulo mm. For example,

3(5)+7(−2)=13(5)+7(-2)=1

shows that 55 is the inverse of 33 modulo 77.

Coprime cancellation and prime divisibility

If gcd⁡(a,b)=1\gcd(a,b)=1 and a∣bca\mid bc, then a∣ca\mid c. To see this, multiply ax+by=1ax+by=1 by cc:

acx+bcy=c.acx+bcy=c.

Both terms on the left are divisible by aa.

For a prime number pp, this yields Euclid's lemma:

p∣ab⟹p∣a or p∣b.p\mid ab\quad\Longrightarrow\quad p\mid a\ \text{or}\ p\mid b.

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 gcd⁡(m,n)=1\gcd(m,n)=1 and

um+vn=1,um+vn=1,

then the simultaneous congruences

z≡r(modm),z≡s(modn)z\equiv r\pmod m,\qquad z\equiv s\pmod n

are satisfied by

z=rvn+sum.z=rvn+sum.

The solution is unique modulo mnmn.

Generalizations

More than two integers

For integers a1,…,ana_1,\ldots,a_n, not all zero, there exist integers x1,…,xnx_1,\ldots,x_n such that

a1x1+⋯+anxn=gcd⁡(a1,…,an).a_1x_1+\cdots+a_nx_n=\gcd(a_1,\ldots,a_n).

This follows by repeatedly applying the two-integer identity, using

gcd⁡(a1,a2,a3)=gcd⁡(gcd⁡(a1,a2),a3).\gcd(a_1,a_2,a_3)=\gcd(\gcd(a_1,a_2),a_3).

In particular, the integers collectively have greatest common divisor 11 exactly when an integer combination of them equals 11. Collective coprimality does not require pairwise coprimality: 6,10,156,10,15 have greatest common divisor 11, and

6+10−15=1,6+10-15=1,

although every pair has a common divisor greater than 11.

Polynomials over a field

If f,gf,g are polynomials in one variable over a field FF, and are not both zero, then there exist u,v∈F[x]u,v\in F[x] such that

uf+vg=gcd⁡(f,g).uf+vg=\gcd(f,g).

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 Q[x]\mathbb Q[x],

(x2+1)−x(x)=1,(x^2+1)-x(x)=1,

so x2+1x^2+1 and xx are relatively prime.

Ideals and Bézout domains

In the language of abstract algebra, the integer identity says

(a,b)=(d),(a,b)=(d),

where (a,b)(a,b) is the ideal generated by a,ba,b, and (d)(d) 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 Q[s,t]\mathbb Q[s,t], the polynomials ss and tt have greatest common divisor 11, but no polynomials u,vu,v satisfy

su+tv=1.su+tv=1.

Evaluating at s=t=0s=t=0 would give 0=10=1. 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.