Wikipedia · einfach zusammengefasst · Stand
Lemma von Bézout
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 …
Inhalt6 Abschnitte
Kernaussage
Das Lemma von Bézout ist eine grundlegende Aussage der Zahlentheorie. Es besagt: Der größte gemeinsame Teiler zweier ganzer Zahlen a und b lässt sich als Linearkombination dieser beiden Zahlen mit ganzzahligen Koeffizienten darstellen.
Formal gilt: ∀ a,b ∈ Z ∃ s,t ∈ Z : ggT(a,b) = s · a + t · b.
Eine Linearkombination bedeutet hier, dass a und b jeweils mit ganzen Zahlen s und t multipliziert und dann addiert werden. Die Zahlen s und t heißen Koeffizienten.
Teilerfremdheit und Verallgemeinerung
Sind a und b teilerfremd, also ggT(a,b) = 1, dann gibt es ganze Zahlen s und t mit: 1 = s · a + t · b.
Auch die Umkehrung gilt: Wenn es ganze Zahlen s und t gibt, sodass sa + tb = 1 ist, dann ist ggT(a,b) = 1. Damit liefert das Lemma ein Kriterium dafür, ob zwei ganze Zahlen teilerfremd sind.
Die Koeffizienten s und t können mit dem erweiterten euklidischen Algorithmus effizient berechnet werden.
Das Lemma gilt auch für mehr als zwei ganze Zahlen. Für ganze Zahlen a₁, …, aₙ existieren ganzzahlige Koeffizienten s₁, …, sₙ mit: s₁a₁ + … + sₙaₙ = ggT(a₁, …, aₙ).
Als Linearkombination von a und b lassen sich genau alle ganzzahligen Vielfachen von ggT(a,b) darstellen. Andere ganze Zahlen lassen sich nicht so darstellen. Die Frage, welche Zahlen mit natürlichen Zahlen als Koeffizienten darstellbar sind, gehört zum Münzproblem.
Beweisidee
Der Beweis verwendet die Division mit Rest. Deshalb lässt sich die Idee auch auf euklidische Ringe übertragen.
Für a = 0 kann man s = 0 und t = ±1 wählen. Danach wird angenommen, dass a ≠ 0 gilt. Man betrachtet alle Zahlen der Form x = s · a + t · b mit s,t ∈ Z und wählt darunter die kleinste positive Zahl d = s · a + t · b.
Da ggT(a,b) sowohl a als auch b teilt, teilt ggT(a,b) auch jede Linearkombination von a und b, also auch d.
Dann zeigt man umgekehrt, dass d sowohl a als auch b teilt. Dazu schreibt man mit Division mit Rest a = q · d + r mit 0 ≤ r < d. Setzt man d = s · a + t · b ein, erhält man r = (1 − q · s) · a + (−q · t) · b. Also ist r ebenfalls eine Linearkombination von a und b. Weil d als kleinste positive solche Zahl gewählt wurde, muss r = 0 sein. Also teilt d die Zahl a. Genauso zeigt man, dass d auch b teilt.
Damit ist d ein gemeinsamer Teiler von a und b. Zugleich wird d von ggT(a,b) geteilt. Daraus folgt d = ggT(a,b).
Formulierung mit Idealen
In der Ringtheorie kann man das Lemma mit Idealen ausdrücken. Ein Ideal ist eine bestimmte Teilmenge eines Ringes, die sich für algebraische Rechnungen gut verhält. Ein Hauptideal ist ein Ideal, das von einem einzigen Element erzeugt wird, etwa aR.
Für einen Ring R gilt, dass die Hauptideale aR und bR im Hauptideal ggT(a,b)R enthalten sind. Daher ist auch aR + bR in ggT(a,b)R enthalten.
Für R = Z, also den Ring der ganzen Zahlen, und allgemein für euklidische Ringe kann man das Lemma so formulieren: aR + bR = cR, wenn c = ggT(a,b).
In Hauptidealringen ist jedes Ideal ein Hauptideal. Deshalb gibt es zu Elementen a und b immer ein Element c mit aR + bR = cR. Dieses c ist ein gemeinsamer Teiler von a und b und zugleich eine Linearkombination von a und b. In diesem Sinn gilt das Lemma von Bézout in Hauptidealringen, wenn man c als ggT von a und b auffasst.
Wichtige Folgerungen
Das Lemma von Bézout ist in der Mathematik, besonders in der Zahlentheorie, von elementarer Bedeutung. Aus ihm lassen sich mehrere wichtige Ergebnisse ableiten:
- das Lemma von Euklid, aus dem die Eindeutigkeit der Primzahlzerlegung folgt,
- der chinesische Restsatz,
- ein Kriterium für die Lösbarkeit linearer diophantischer Gleichungen,
- ein Kriterium für die Invertierbarkeit von Restklassen.
Eine lineare diophantische Gleichung ist eine Gleichung mit ganzzahligen Lösungen. Restklassen treten beim Rechnen mit Resten auf, zum Beispiel in der modularen Arithmetik.
Praktisches Beispiel
Ein Beispiel aus dem Artikel verwendet 2-Cent- und 5-Cent-Münzen. Da 2 und 5 Primzahlen sind, ist ihr größter gemeinsamer Teiler 1. Deshalb ist jeder Cent-Betrag als ganzzahlige Linearkombination von 2 und 5 darstellbar.
Ein negativer Koeffizient kann dabei als Wechselgeld verstanden werden. Dadurch kann man mit 2-Cent- und 5-Cent-Münzen zusammen mit Geld und Wechselgeld genau alle Cent-Beträge bezahlen.