states that if a
with greatest common divisor d
, then there exist integers x
- ax + by = d.
as above can be determined with the extended Euclidean algorithm
; they are not uniquely determined however.
For example, the greatest common divisor of 12 and 42 is 6, and we can write
- (-3)·12 + 1·42 = 6
- 4·12 + (-1)·42 = 6.
Bézout's identity works not only in the ring
of integers, but also in any other principal ideal domain
That is, if R
is a PID, and a
are elements of R
, and d
is a greatest common divisor of a
then there are elements x
such that ax
Bézout's identity is named for the 18th century French mathematician Étienne Bézout.