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.
a
{\ displaystyle a}
b
{\ displaystyle b}
a
{\ displaystyle a}
b
{\ displaystyle b}
Statement and formal presentation
Expressed formally, the following applies:
∀
a
,
b
∈
Z
∃
s
,
t
∈
Z
:
gcd
(
a
,
b
)
=
s
⋅
a
+
t
⋅
b
{\ 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
a
{\ displaystyle a}
b
{\ displaystyle b}
s
,
t
∈
Z
{\ displaystyle s, t \ in \ mathbb {Z}}
1
=
s
⋅
a
+
t
⋅
b
{\ displaystyle 1 = s \ cdot a + t \ cdot b}
applies.
comment
A kind of reversal also applies here: if there is with , then there is .
s
,
t
∈
Z
{\ displaystyle s, t \ in \ mathbb {Z}}
s
a
+
t
b
=
1
{\ displaystyle sa + tb = 1}
gcd
(
a
,
b
)
=
1
{\ displaystyle \ operatorname {ggT} (a, b) = 1}
The coefficients and can be calculated efficiently using the extended Euclidean algorithm .
s
{\ displaystyle s}
t
{\ displaystyle t}
The lemma can be generalized to more than two whole numbers: If there are whole numbers, then there are integral coefficients with
a
1
,
...
,
a
n
{\ displaystyle a_ {1}, \ dotsc, a_ {n}}
s
1
,
...
,
s
n
{\ displaystyle s_ {1}, \ dotsc, s_ {n}}
s
1
a
1
+
⋯
+
s
n
a
n
=
gcd
(
a
1
,
...
,
a
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 .
a
=
0
{\ displaystyle a = 0}
s
=
0
{\ displaystyle s = 0}
t
=
±
1
{\ displaystyle t = \ pm 1}
a
≠
0
{\ displaystyle a \ neq 0}
x
=
s
⋅
a
+
t
⋅
b
{\ displaystyle x = s \ cdot a + t \ cdot b}
s
,
t
∈
Z
{\ displaystyle s, t \ in \ mathbb {Z}}
≠
0
{\ displaystyle \ neq 0}
d
=
s
⋅
a
+
t
⋅
b
{\ displaystyle d = s \ cdot a + t \ cdot b}
gcd
(
a
,
b
)
{\ displaystyle \ operatorname {ggT} (a, b)}
a
{\ displaystyle a}
b
{\ displaystyle b}
gcd
(
a
,
b
)
{\ displaystyle \ operatorname {ggT} (a, b)}
d
{\ 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 .
d
{\ displaystyle d}
a
{\ displaystyle a}
b
{\ displaystyle b}
a
{\ displaystyle a}
q
⋅
d
+
r
{\ displaystyle q \ cdot d + r}
0
≤
r
<
d
{\ displaystyle 0 \ leq r <d}
d
{\ displaystyle d}
s
⋅
a
+
t
⋅
b
{\ displaystyle s \ cdot a + t \ cdot b}
r
{\ displaystyle r}
r
=
(
1
-
q
⋅
s
)
⋅
a
+
(
-
q
⋅
t
)
⋅
b
{\ displaystyle r = (1-q \ cdot s) \ cdot a + (- q \ cdot t) \ cdot b}
d
{\ displaystyle d}
r
=
0
{\ displaystyle r = 0}
d
{\ displaystyle d}
a
{\ displaystyle a}
d
{\ displaystyle d}
b
{\ displaystyle b}
d
≤
gcd
(
a
,
b
)
{\ displaystyle d \ leq \ operatorname {ggT} (a, b)}
gcd
(
a
,
b
)
{\ displaystyle \ operatorname {ggT} (a, b)}
d
{\ displaystyle d}
d
=
gcd
(
a
,
b
)
{\ 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)
a
R.
{\ displaystyle aR}
b
R.
{\ displaystyle bR}
gcd
(
a
,
b
)
R.
{\ displaystyle \ operatorname {ggT} (a, b) \; R}
a
R.
+
b
R.
{\ displaystyle aR + bR}
gcd
(
a
,
b
)
R.
{\ displaystyle \ operatorname {ggT} (a, b) \; R}
R.
=
Z
{\ displaystyle R = \ mathbb {Z}}
a
R.
+
b
R.
=
c
R.
{\ displaystyle aR + bR = cR}
, if
c
=
gcd
(
a
,
b
)
{\ 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 .
a
{\ displaystyle a}
b
{\ displaystyle b}
c
{\ displaystyle c}
a
R.
+
b
R.
{\ displaystyle aR + bR}
c
R.
{\ displaystyle cR}
c
{\ displaystyle c}
a
{\ displaystyle a}
b
{\ displaystyle b}
a
{\ displaystyle a}
b
{\ displaystyle b}
c
{\ displaystyle c}
gcd
{\ displaystyle \ operatorname {ggT}}
a
{\ displaystyle a}
b
{\ 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
References and comments
↑ Because if and is a common factor , so and , then, is , therefore, a factor of 1. ■
d
∈
Z
{\ displaystyle d \ in \ mathbb {Z}}
a
{\ displaystyle a}
b
{\ displaystyle b}
a
=
a
′
d
{\ displaystyle a = a ^ {\ prime} d}
b
=
b
′
d
{\ displaystyle b = b ^ {\ prime} d}
1
=
s
a
′
d
+
t
b
′
d
=
(
s
a
′
+
t
b
′
)
d
=
1
{\ displaystyle 1 = sa ^ {\ prime} d + tb ^ {\ prime} d = (sa ^ {\ prime} + tb ^ {\ prime}) \, d = 1}
d
{\ displaystyle d}
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">