Linearkombinationen

Der Euklidische Algorithmus liefert mehr als eine effiziente Berechnung des größten gemeinsamen Teilers zweier Zahlen. Durch Rückwärtsrechnen können wir eine Darstellung des größten gemeinsamen Teilers als Linearkombination der beiden Zahlen finden:

Beispiel: Der ggT als Linearkombination

In Fortsetzung des vorangehenden Beispiels rechnen wir zurück:

(129, 33)	= 3
	= 33 − 1 · 30
	= 33 − 1 (129 − 3 · 33)
	= 4 · 33 − 1 · 129.

Damit haben wir den größten gemeinsamen Teiler von a und b als Linearkombination von a und b dargestellt. Die Koeffizienten dieser Linearkombination sind 4 und −1.

Allgemein liefert dieses Rückwärtsrechnen:

Satz (Lemma von Bézout, I)

Seien a, b  ∈  ℤ. Dann ist (a, b) eine Linearkombination von a und b, die mit Hilfe der Version II des Euklidischen Algorithmus gefunden werden kann.

Beweis

Wir dürfen a > b > 0 annehmen. Wir führen den Euklidischen Algorithmus in der Variante II mit Ergebnis a_n + 1 durch und zeigen für alle k = 0, …, n + 1:

a_k ist eine Linearkombination von a = a₀ und b = a₁.

Die Aussage ist klar für k = 0 und k = 1. Für k = 2, …, n + 1 gilt:

a_k = a_k − 2 − q_k − 2 a_k − 1.

Dies zeigt, dass a_k eine Linearkombination von a_k − 2 und a_k − 1 ist. Damit folgt die Behauptung durch eine endliche starke Induktion, denn eine Linearkombination von Linearkombinationen ist wieder eine Linearkombination.

Klarheit über alle möglichen Linearkombinationen schafft:

Satz (Lemma von Bézout, II)

Seien a, b  ∈  ℤ. Dann gilt:

{ na + mb | n, m  ∈  ℤ } = { d (a, b) | d  ∈  ℤ }.

Mit anderen Worten: Die Linearkombinationen zweier Zahlen sind genau die ganzzahligen Vielfachen des größten gemeinsamen Teilers der beiden Zahlen.

Beweis

zu ⊆: Sei c = na + mb eine Linearkombination von a und b. Dann ist (a, b) ein Teiler von c nach unserer Teilbarkeitseigenschaft (T7) (ein gemeinsamer Teiler von a und b ist auch ein Teiler einer Linearkombination von a und b). Folglich gibt es ein d mit d (a, b) = c. Dies zeigt, dass die Menge auf der linken Seite eine Teilmenge der Menge auf der rechten Seite ist.

zu ⊇: Wir wissen, dass (a, b) eine Linearkombination von a und b ist. Da ein ganzzahliges Vielfaches einer Linearkombination zweier Zahlen wieder eine solche ist, ist d (a, b) für alle ganzen Zahlen d eine Linearkombination von a und b. Damit ist die Menge auf der rechten Seite eine Teilmenge der Menge auf der linken Seite.

Beispiel

Die Linearkombinationen der Zahlen 15 und 6 sind nach dem Satz genau die ganzzahligen Vielfachen von 3 = (15, 6). Mit Hilfe einer Tabelle können wir die Struktur dieser Linearkombinationen veranschaulichen:

	−18	−12	−6	0	6	12	18
−45	−63	−57	−51	−45	−39	−33	−27
−30	−48	−42	−36	−30	−24	−18	−12
−15	−33	−27	−21	−15	−9	−3	3
0	−18	−12	−6	0	6	12	18
15	−3	3	9	15	21	27	33
30	12	18	24	30	36	42	48
45	27	33	39	45	51	57	63

Linearkombinationen der Zahlen 6 und 15

Der Euklidische Algorithmus liefert 15 = 2 · 6 + 3, sodass

3 = 1 · 15 − 2 · 6.

Eine nichttriviale Darstellung der 0 erhalten wir mit 30 = [ 15, 6 ] durch

0 = 30 − 30 = 2 · 15 − 5 · 6.

Damit erhalten wir die zweite 3 der Tabelle:

3 = 3 − 0 = 1 · 15 − 2 · 6 − 2 · 15 + 5 · 6 = −1 · 15 + 3 · 6.