Lemma of Bézout

The lemma Bézout (after Etienne Bézout 1730-1783) () in the number theory says that the greatest common divisor of two integers and as a linear combination of and represent with integer coefficients can. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

Statement and formal presentation

Expressed formally, the following applies:

${\displaystyle \forall a,b\in \mathbb {Z} \ \exists s,t\in \mathbb {Z} :\operatorname {ggT} (a,b)=s\cdot a+t\cdot b}$

Are and coprime , then exist such that ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle s,t\in \mathbb {Z} }$

${\displaystyle 1=s\cdot a+t\cdot b}$

applies.

comment

A kind of reversal also applies here: if there is with , then there is . ${\displaystyle s,t\in \mathbb {Z} }$ ${\displaystyle sa+tb=1}$ ${\displaystyle \operatorname {ggT} (a,b)=1}$

The coefficients and can be calculated efficiently using the extended Euclidean algorithm . ${\displaystyle s}$ ${\displaystyle t}$

The lemma can be generalized to more than two whole numbers: If there are whole numbers, then there are integral coefficients with ${\displaystyle a_{1},\dotsc ,a_{n}}$ ${\displaystyle s_{1},\dotsc ,s_{n}}$

${\displaystyle s_{1}a_{1}+\dotsb +s_{n}a_{n}=\operatorname {ggT} (a_{1},\dotsc ,a_{n})}$.

More generally, Bézout's lemma holds true in every principal ideal ring , even in a non-commutative one ; for the exact statements see there.

The question of which numbers can even be represented as coefficients with natural numbers is the subject of the coin problem .

proof

The proof of the lemma is based on the possibility of division with remainder . Thus it can easily be transferred to Euclidean rings .

For and can be set, so we assume, without loss of generality , that holds. Among all the numbers with there are certainly also those that are positive and are. Be the smallest number among these. Since both and shares, shares also . ${\displaystyle a=0}$ ${\displaystyle s=0}$ ${\displaystyle t=\pm 1}$ ${\displaystyle a\neq 0}$ ${\displaystyle x=s\cdot a+t\cdot b}$ ${\displaystyle s,t\in \mathbb {Z} }$ ${\displaystyle \neq 0}$ ${\displaystyle d=s\cdot a+t\cdot b}$ ${\displaystyle \operatorname {ggT} (a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \operatorname {ggT} (a,b)}$ ${\displaystyle d}$

We now show that and is also a factor . Division by remainder gives us a representation of the form , where . If you insert for the representation and solve the equation for , you get . Because of the minimality of must be, so is a divisor of . Correspondingly, it also holds that is a divisor of , and thus holds . We had already seen before that is a divisor of . So it applies . ${\displaystyle d}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle q\cdot d+r}$ ${\displaystyle 0\leq r<d}$ ${\displaystyle d}$ ${\displaystyle s\cdot a+t\cdot b}$ ${\displaystyle r}$ ${\displaystyle r=(1-q\cdot s)\cdot a+(-q\cdot t)\cdot b}$ ${\displaystyle d}$ ${\displaystyle r=0}$ ${\displaystyle d}$ ${\displaystyle a}$ ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle d\leq \operatorname {ggT} (a,b)}$ ${\displaystyle \operatorname {ggT} (a,b)}$ ${\displaystyle d}$ ${\displaystyle d=\operatorname {ggT} (a,b)}$

Main ideals

If one uses the concept of the ideal from ring theory , it is fundamentally true that the main ideals and are contained in the main ideal . So also the ideal is to contain. One can also formulate Bézout's lemma in such a way that applies to the ring (or generally to Euclidean rings) ${\displaystyle aR}$ ${\displaystyle bR}$ ${\displaystyle \operatorname {ggT} (a,b)\;R}$ ${\displaystyle aR+bR}$ ${\displaystyle \operatorname {ggT} (a,b)\;R}$ ${\displaystyle R=\mathbb {Z} }$

${\displaystyle aR+bR=cR}$, if ${\displaystyle c=\operatorname {ggT} (a,b)}$

Main ideal rings are rings in which every ideal is a main ideal. There is always an element for elements and the ring , so that the ideal is the main ideal . is then on the one hand a common divisor of and , and on the other hand a linear combination of and . In main ideal rings, Bézout's lemma applies to a certain extent by definition if the element is regarded as that of and . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle aR+bR}$ ${\displaystyle cR}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \operatorname {ggT} }$ ${\displaystyle a}$ ${\displaystyle b}$

Inferences

Bézout's lemma is of elementary importance for mathematics and especially for number theory. So you can z. B. derive the lemma of Euclid , which results in the uniqueness of the prime number decomposition . The Chinese remainder theorem is a further consequence of the Bézout lemma. For linear Diophantine equations , Bézout's lemma yields a criterion for their solvability.

literature

• Kurt Meyberg: Algebra - Part 1 . Hanser 1980, ISBN 3-446-13079-9 , p. 43
• Stephen Fletcher Hewson: A Mathematical Bridge: An Intuitive Journey in Higher Mathematics . World Scientific, 2003, ISBN 978-981-238-555-0 , pp. 111 ff.

Web links

• Eric W. Weisstein : Bezout's Identity . In: MathWorld (English).
• Bézout's Lemma in the ProofWiki

References and comments

1. ↑ Because if and is a common factor , so and , then, is , therefore, a factor of 1. ■ ${\displaystyle d\in \mathbb {Z} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a=a^{\prime }d}$ ${\displaystyle b=b^{\prime }d}$ ${\displaystyle 1=sa^{\prime }d+tb^{\prime }d=(sa^{\prime }+tb^{\prime })\,d=1}$ ${\displaystyle d}$