Lemma von Bézout

Das Lemma von Bézout (nach Étienne Bézout (1730–1783)) in der Zahlentheorie besagt, dass sich der 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 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: 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> teilerfremd (das ist der Spezialfall mit <math>\operatorname{ggT}(a,b) = 1</math>), existieren <math>s,t\in\mathbb{Z}</math>, sodass

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 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 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ünzproblems.

Beweis

Der Beweis des Lemmas basiert auf der Möglichkeit der Division mit Rest. Somit lässt er sich leicht auf 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 Ideals aus der Ringtheorie, so gilt grundsätzlich, dass die Hauptideale <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>

Hauptidealringe 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 chinesische Restsatz,
ein Kriterium für die Lösbarkeit linearer diophantischer Gleichungen,
ein Kriterium für die 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

Eric W. Weisstein: Bezout’s Identity. In: MathWorld (englisch).
Lemma Bézout’s Lemma im ProofWiki

Einzelnachweise und Anmerkungen