Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Bézout's identity
Summary
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here 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. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm, and this pair is, in the case of integers one of the two pairs such that and equality occurs only if one of a and b is a multiple of the other.
As an example, the greatest common divisor of 15 and 69 is 3, and 3 can be written as a combination of 15 and 69 as 3 = 15 × (−9) + 69 × 2, with Bézout coefficients −9 and 2.
Many other theorems in elementary number theory, such as Euclid's lemma or the Chinese remainder theorem, result 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.
If a and b are not both zero and one pair of Bézout coefficients (x, y) has been computed (for example, using the extended Euclidean algorithm), all pairs can be represented in the form
where k is an arbitrary integer, d is the greatest common divisor of a and b, and the fractions simplify to integers.
If a and b are both nonzero, then exactly two of these pairs of Bézout coefficients satisfy
and equality may occur only if one of a and b divides the other.
This relies on a property of Euclidean division: given two non-zero integers c and d, if d does not divide c, there is exactly one pair (q, r) such that and and another one such that and
The two pairs of small Bézout's coefficients are obtained from the given one (x, y) by choosing for k in the above formula either of the two integers next to .
The extended Euclidean algorithm always produces one of these two minimal pairs.
Let a = 12 and b = 42, then gcd (12, 42) = 6. Then the following Bézout's identities are had, with the Bézout coefficients written in red for the minimal pairs and in blue for the other ones.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.