Bezout's Identity

Integral Domains, Bezout's Identity

Bezout's Identity

In the ring of integers, gcd(a,b) can always be written as a linear combination of a and b. Bezout (biography) showed that the same is true in a pid, although there may not be an efficient algorithm for deriving the gcd, or the linear combination that produces the gcd.

In a pid, let a and b generate the principal ideal c*R. Clearly c divides a and b. If g = gcd(a,b), g divides a and b, and g*R contains the ideals a*R and b*R, and hence c*R. thus g divides c. Yet c divides g, hence c = g. Since g is generated by a and b, it is some linear combination of a and b, using coefficients from R.

Generalize this to a finite list of elements. Their common gcd is a linear combination of those elements. For instance:

   g = ax + by. 
   h = gcd(g,c). 
   h = wg + zc. 
   h = wxa + wyb + zc.

Proceed by induction on the number of elements in the set.

Bezout's identity fails for arbitrary ufds. In Z[x], the integer polynomials over x, 2 and x are coprime, yet no linear combination of 2 and x yields 1.