Bézout's identity

In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is a theorem which relates two arbitrary integers with their greatest common divisor. The theorem's statement is as follows:

Bézout's identity—Let $a$ and $b$ be integers with greatest common divisor $d$ . Then there exist integers $x$ and $y$ such that $ax + by = d$ . Moreover, the integers of the form $az + bt$ are exactly the multiples of $d$ .

(The greatest common divisor of $0$ and $0$ is taken to be $0$ .) The integers $x$ and $y$ are called Bézout coefficients for $(a, b)$ ; they are not unique. The extended Euclidean algorithm can be used to compute a minimal pair of Bézout coefficients, meaning they satisfy $|x|\leq |b/d|$ and $|y|<|a/d|$ ; equality occurs only if one of $a$ and $b$ is a multiple of the other, and otherwise there exist exactly two minimal pairs.

As an example, the greatest common divisor of $a=15$ and $b=69$ is $d=3$ , which can be written as the linear combination $ax+by=15(-9)+69(2)=3$ with Bézout coefficients $(x,y)=(-9,2)$ , which are minimal since $9<69/3=23$ and $2<15/3=5$ . The other minimal Bézout coefficients are $(x,y)=(-9+23,2-5)=(14,-3)$ .

Many other theorems in elementary number theory, such as Euclid's lemma or the Chinese remainder theorem, can be formally deduced from Bézout's identity.

A Bézout domain is an integral domain in which Bézout's identity holds. In particular, Bézout's identity holds in principal ideal domains. Every theorem that results from Bézout's identity is thus true in all principal ideal domains.