Quelltext der Seite Lemma von Bézout

Das '''Lemma von Bézout''' (nach [[Étienne Bézout]] (1730–1783)) in der [[Zahlentheorie]] besagt, dass sich der [[größter gemeinsamer Teiler|größte gemeinsame Teiler]] zweier ganzer Zahlen <math>a</math> und <math>b</math> als [[Linearkombination]] von <math>a</math> und <math>b</math> mit ganzzahligen Koeffizienten darstellen lässt. 

Bézout beschrieb die Aussage 1766 im dritten Band seiner vierbändigen ''Cours de Mathematiques a l’usage des Gardes du Pavillon et de la Marine'' und verallgemeinerte sie dort auf [[Polynom|Polynome]]. Allerdings war die Aussage bezogen auf ganze Zahlen bereits 142 Jahre früher von [[Claude Gaspard Bachet de Méziriac]] aufgestellt worden, der sie als Proposition XVIII in seinem 1624 erschienenen Buch ''Problemes plaisants et delectables qui se fonts par les nombres'' bewies.<ref>Wolfgang K. Seiler: [http://hilbert.math.uni-mannheim.de/~seiler/ZT18/zahlen18.pdf Zahlentheorie]. Vorlesungsskript, Uni Mannheim, 2018</ref>

== Aussage und formale Darstellung ==
Formal ausgedrückt gilt:
: <math>\forall a,b\in \Z \ \exist s,t\in \Z:  \operatorname{ggT}(a,b) = s \cdot a + t \cdot b</math>

Sind <math>a</math> und <math>b</math> [[Teilerfremdheit|teilerfremd]] (das ist der Spezialfall mit <math>\operatorname{ggT}(a,b) = 1</math>), existieren <math>s,t\in\mathbb{Z}</math>, sodass
: <math>1 = s \cdot a + t \cdot b</math>
gilt. Außerdem gilt auch eine Art Umkehrung; gibt es nämlich <math>s,t\in \Z </math> mit <math> s a + t b = 1</math>, dann ist <math>\operatorname{ggT}(a,b) = 1</math>.<ref>Denn ist <math>d\in \Z </math> ein gemeinsamer Teiler von <math>a</math> und <math>b</math>, also <math>a=a^\prime d</math> und <math>b=b^\prime d</math>, dann ist <math> 1 = s a^\prime d + t b^\prime d = (s a^\prime + t b^\prime) \, d = 1</math>, also <math>d </math> ein Teiler von 1. ■</ref>

Die Koeffizienten <math>s</math> und <math>t</math> können mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] effizient berechnet werden.

Das Lemma lässt sich auf mehr als zwei ganze Zahlen verallgemeinern: Sind <math>a_1, \dotsc, a_n</math> ganze Zahlen, dann existieren ganzzahlige Koeffizienten <math>s_1, \dotsc, s_n</math> mit
: <math>s_1 a_1 + \dotsb + s_n a_n = \operatorname{ggT}(a_1,\dotsc,a_n)</math>.

Allgemeiner gilt das Lemma von Bézout in jedem [[Hauptidealring]], sogar in einem [[Hurwitzquaternion#Euklidizität|nicht-kommutativen]]; für die genauen Aussagen siehe dort.

Als Linearkombination von <math>a</math> und <math>b</math> lässt sich nicht nur <math>\operatorname{ggT}(a,\,b)</math> darstellen, sondern alle ganzzahligen Vielfache des <math>\operatorname{ggT}</math>. Alle anderen Zahlen lassen sich dagegen nicht darstellen.

Die Frage, welche Zahlen sich sogar mit natürlichen Zahlen als Koeffizienten darstellen lassen, ist Gegenstand des [[Münzproblem]]s.

== Beweis ==

Der Beweis des Lemmas basiert auf der Möglichkeit der [[Division mit Rest]]. Somit lässt er sich leicht auf
[[Euklidischer Ring|euklidische Ringe]] übertragen.

Für <math>a=0</math> kann <math>s=0</math> und <math>t=\pm 1</math> gesetzt werden, also nehmen wir [[ohne Beschränkung der Allgemeinheit]] an, dass <math>a \neq 0</math> gilt.  Unter allen Zahlen <math>x = s \cdot a + t \cdot b</math> mit <math>s,t\in\mathbb{Z}</math> gibt es sicher auch solche, die positiv und <math> \neq 0</math> sind. Sei <math>d = s \cdot a + t \cdot b</math> die kleinste Zahl unter diesen. Da <math>\operatorname{ggT}(a,b)</math> sowohl <math>a</math> als auch <math>b</math> teilt, teilt <math>\operatorname{ggT}(a,b)</math> auch <math>d</math> .

Wir zeigen nun, dass <math>d</math> auch ein Teiler von <math>a</math> und <math>b</math> ist. Die Division mit Rest liefert uns eine Darstellung <math>a</math> der Form <math>q \cdot d + r</math>, wobei <math>0 \leq r < d</math> . Setzt man für <math>d</math> die Darstellung <math>s \cdot a + t \cdot b</math> ein und löst die Gleichung nach <math>r</math> auf, so erhält man <math>r = (1 - q \cdot s) \cdot a + (- q \cdot t) \cdot b</math>. Wegen der Minimalität von <math>d</math> muss <math>r = 0</math> sein, also ist <math>d</math> ein Teiler von <math>a</math>. Entsprechend gilt auch, dass <math>d</math> ein Teiler von <math>b</math> ist, und somit gilt <math>d \leq \operatorname{ggT}(a,b)</math>. Vorher hatten wir schon gesehen, dass <math>\operatorname{ggT}(a,b)</math> ein Teiler von <math>d</math> ist. Also gilt <math> d = \operatorname{ggT}(a,b)</math>.

== Hauptideale ==
Verwendet man den Begriff des [[Ideal (Ringtheorie)|Ideals]] aus der [[Ringtheorie]], so gilt grundsätzlich, dass die [[Hauptideal]]e <math>a R</math> und <math>b R</math> in dem Hauptideal <math>\operatorname{ggT}(a,b)\;R</math> enthalten sind. Also ist auch das Ideal <math>a R + b R</math> in <math>\operatorname{ggT}(a,b)\;R</math> enthalten. Man kann das Lemma von Bézout auch so formulieren, dass für den Ring <math>R=\Z</math> (oder allgemein für euklidische Ringe) gilt
: <math>a R + b R = c R</math>, wenn <math>c = \operatorname{ggT}(a,b)</math>
[[Hauptidealring]]e sind Ringe, in denen jedes Ideal ein Hauptideal ist. Dort gibt es zu Elementen <math>a</math> und <math>b</math> des Ringes immer ein Element <math>c</math>, sodass das Ideal <math>a R + b R</math> das Hauptideal <math>c R</math> ist. <math>c</math> ist dann einerseits ein gemeinsamer Teiler von <math>a</math> und <math>b</math>, und andererseits eine Linearkombination von <math>a</math> und <math>b</math>. In Hauptidealringen gilt daher gewissermaßen definitionsgemäß das Lemma von Bézout, wenn man das Element <math>c</math> als den <math>\operatorname{ggT}</math> von <math>a</math> und <math>b</math> ansieht.

== Folgerungen ==
Das Lemma von Bézout ist für die Mathematik und besonders für die Zahlentheorie von elementarer Bedeutung. So lassen sich damit ableiten
* das [[Lemma von Euklid]], welches die Eindeutigkeit der [[Primzahlzerlegung]] zur Folge hat, 
* der [[Chinesischer Restsatz|chinesische Restsatz]],
* ein Kriterium für die Lösbarkeit [[Lineare diophantische Gleichung|linearer diophantischer Gleichungen]],
* ein Kriterium für die [[Restklassenring#Invertierbarkeit und Inversenberechnung|Invertierbarkeit von Restklassen]].

== Praktische Anwendung ==
Ein praktisches Beispiel, das sich direkt auch dem Lemma von Bézout ergibt, ist, dass man mit 2-Cent- und 5-Cent-Münzen genau alle Beträge durch Geld und Wechselgeld bezahlen kann. Da 2 und 5 Primzahlen sind, ist ihr größter gemeinsamer Teiler 1 und damit ist jeder Cent-Betrag als eine Linearkombination darstellbar, ein möglicher negativer Wert steht dabei für das Wechselgeld (siehe auch [[Münzproblem]]).

== Literatur ==
* Kurt Meyberg: ''Algebra – Teil 1''. Hanser 1980, ISBN 3-446-13079-9, S. 43
* Stephen Fletcher Hewson: ''A Mathematical Bridge: An Intuitive Journey in Higher Mathematics''. World Scientific, 2003, ISBN 978-981-238-555-0, S. 111 ff.

== Weblinks ==
* {{MathWorld |id=BezoutsIdentity |title=Bezout’s Identity}}
* [https://proofwiki.org/wiki/B%C3%A9zout%27s_Identity Lemma Bézout’s Lemma] im ProofWiki

== Einzelnachweise und Anmerkungen ==
<references />

[[Kategorie:Satz (Zahlentheorie)|Bezout, Lemma von]]