Main Index
Number Theory
Arithmetics
Multiplication
Divisibility
Greatest common divisor
Subject Index
comment on the page
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:
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:
Štefan Porubský: Extended Euclid’s Algorithm.