Main Index Number Theory Arithmetics Multiplication Divisibility Greatest common divisor
 Subject Index
comment on the page

Extended Euclid’s algorithm

The next result is often called Bézout’s theorem after Étienne Bézout (1730-1783), who proved it actually for polynomials. This result formulated for integers can be found earlier in the work Claude Gaspard Bachet de Méziriac (1581-1638).

Theorem: Given two integers , , theth1re exists integers , such that

(1)

where is the greatest common divisor of   and .

Two remarks:

• is the smallest positive integer for which there are integer solutions and for the equation (1).
• with every multiple of can be written in form ( 1) with suitable and .

The numbers and are not uniquely determined. Given one such couple , there are infinitely many of them

(2)

Corollary: For any integers with greatest common divisor there exist integers such that

(3)

The greatest common divisor of integers is the smallest positive integer that can be written as a linear combination of the form (3).  

One form how to prove the Corollary is to write

(4)

Bázout’s identity is true for principal ideal domains in general, although there may not be an efficient algorithm for finding the greatest common divisor here, or the required linear combination that produces the greatest common divisor. The result as such for PID’s follows easily from a non-constructive argument that the ideal generated by and is principal, and its generator is the greatest common divisor of and .

An integral domain in which Bézout's identity holds is called a Bézout domain.

Note, that Bezout's identity fails for general unique factorization domains. For instance, in , the ring of polynomials with integers coefficients, the polynomials and , are obviously coprime for all , yet it is impossible to write their greatest common divisor as a  linear combination of   and .

Cite this web-page as: