Bézout's identity

Bézout's identity states that if a and b are integers with greatest common divisor d, then there exist integers x and y such that

ax + by = d.

Numbers x and y 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

and also

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 (PID). That is, if R is a PID, and a and b are elements of R, and d is a greatest common divisor of a and b, then there are elements x and y in R such that ax + by = d.

Bézout's identity is named for the 18th century French mathematician Étienne Bézout.