Lemma von Bézout

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Lemma von Bézout (nach Étienne Bézout (1730–1783)) in der Zahlentheorie besagt, dass sich der größte gemeinsame Teiler \operatorname{ggT}(a,b) zweier ganzer Zahlen a und b, von denen mindestens eine ungleich  0 ist, als Linearkombination von a und b mit ganzzahligen Koeffizienten darstellen lässt:

\operatorname{ggT}(a,b) = s \cdot a + t \cdot b mit s,t\in\mathbb{Z}.

Sind a und b teilerfremd, dann existieren s,t\in\mathbb{Z}, sodass

1 = s \cdot a + t \cdot b

gilt.

Die Koeffizienten s und t können mit dem erweiterten euklidischen Algorithmus effizient berechnet werden.

Das Lemma lässt sich auf mehr als zwei ganze Zahlen verallgemeinern: Sind a_1, \dotsc, a_n ganze Zahlen, dann existieren ganzzahlige Koeffizienten s_1, \dotsc, s_n mit

s_1 a_1 + \ldots + s_n a_n = \operatorname{ggT}(a_1,\dotsc,a_n).

Allgemeiner gilt das Lemma von Bézout in jedem Hauptidealring, sogar in einem nicht-kommutativen; für die genauen Aussagen siehe dort.

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

Beweis[Bearbeiten]

Der Beweis des Lemmas basiert auf der Möglichkeit der Division mit Rest. Somit lässt er sich leicht auf euklidische Ringe übertragen. Unter allen Zahlen x = s \cdot a + t \cdot b mit s,t\in\mathbb{Z} gibt es sicher auch solche, die positiv und  \neq 0 sind. Sei d = s \cdot a + t \cdot b die kleinste Zahl unter diesen. Da \operatorname{ggT}(a,b) sowohl a als auch b teilt, teilt \operatorname{ggT}(a,b) auch d . Ist d = 1 , ist auch \operatorname{ggT}(a,b) = 1 und die Aussage bewiesen. Für den Fall d > 1 zeigen wir, dass d auch ein Teiler von a und b ist. Die Division mit Rest liefert uns eine Darstellung a der Form q \cdot d + r, wobei 0 \leq r < d . Setzt man für d die Darstellung s \cdot a + t \cdot b ein und löst die Gleichung nach r auf, so erhält man r = (1 - q \cdot s) \cdot a + (- q \cdot t) \cdot b. Wegen der Minimalität von d muss r = 0 sein, also ist d ein Teiler von a. Entsprechend gilt auch, dass d ein Teiler von b ist, und somit gilt d \leq \operatorname{ggT}(a,b). Vorher hatten wir schon gesehen, dass \operatorname{ggT}(a,b) ein Teiler von d ist. Also gilt  d = \operatorname{ggT}(a,b).

Hauptideale[Bearbeiten]

Verwendet man den Begriff des Ideals aus der Ringtheorie, so gilt grundsätzlich, dass die Hauptideale a R und b R in dem Hauptideal \operatorname{ggT}(a,b)\;R enthalten sind. Also ist auch das Ideal a R + b R in \operatorname{ggT}(a,b)\;R enthalten. Man kann das Lemma von Bézout auch so formulieren, dass für den Ring R=\Z (oder allgemein für euklidische Ringe) gilt

a R + b R = c R, wenn c = \operatorname{ggT}(a,b)

Hauptidealringe sind Ringe, in denen jedes Ideal ein Hauptideal ist. Dort gibt es zu Elementen a und b des Ringes immer ein Element c, sodass das Ideal a R + b R das Hauptideal c R ist. c ist dann einerseits ein gemeinsamer Teiler von a und b, und andererseits eine Linearkombination von a und b. In Hauptidealringen gilt daher gewissermaßen definitionsgemäß das Lemma von Bézout, wenn man das Element c als den \operatorname{ggT} von a und b ansieht.

Folgerungen[Bearbeiten]

Das Lemma von Bézout ist für die Mathematik und besonders für die Zahlentheorie von elementarer Bedeutung. So lässt sich damit z.B das Lemma von Euklid ableiten, welches die Eindeutigkeit der Primzahlzerlegung zur Folge hat. Für lineare diophantische Gleichungen ergibt das Lemma von Bézout ein Kriterium für deren Lösbarkeit.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]