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.
Ontological neighbourhood
Related courses (6)
MATH-310: Algebra
This is an introduction to modern algebra: groups, rings and fields.
MATH-328: Algebraic geometry I - Curves
Algebraic geometry is the common language for many branches of modern research in mathematics. This course gives an introduction to this field by studying algebraic curves and their intersection theor
MATH-106(e): Analysis II
Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs
variables.
Related lectures (43)
Polynomial Division & Observer/Controller Approach
Covers polynomial division and observer/controller approach with step-by-step examples.
Method of Undetermined Coefficients
Explores the method of undetermined coefficients for solving non-homogeneous linear differential equations with constant coefficients.
Lag Compensator Design
Explores lag compensator design in control systems, emphasizing phase margin and steady-state error improvement through practical examples.
Related publications (6)
Related concepts (16)
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00.
Greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted . For example, the GCD of 8 and 12 is 4, that is, . In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include highest common factor (hcf), etc.
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor. A fundamental property is that the quotient and the remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder.