Linearkombinationen

Wir beweisen nun auch noch das oben schon angekündigte Ergebnis über Linearkombinationen:

Satz (Linearkombinationen und größter gemeinsamer Teiler)

Sei d = ggT(a, b). Dann können wir mit Hilfe des Euklidischen Algorithmus Zahlen n und m finden derart, dass d = n a + m b.

Beweis

Die Behauptungen sind leicht einzusehen, falls a = b gilt oder falls eine der beiden Zahlen gleich 0 ist. Weiter genügt es, die Aussage für den Fall a > b > 0 zu beweisen. Hierzu seien wieder a₀ > a₁ > a₂ > … > a_i* + 1 = d und q₀, …, q_i* die Zahlen, die der Algorithmus für a = a₀ und b = a₁ liefert.

Wir zeigen durch starke Induktion nach i:

(+) a_i ist eine Linearkombination von a und b für alle 0 ≤ i ≤ i* + 1.

Induktionsschritt i

Sei also a_i′ = n_i′ a + m_i′ b für alle i′ < i (Induktionsvoraussetzung).

Wegen a₀ = a und a₁ = b gilt die Behauptung für i = 0 und i = 1.

Sei also i ≥ 2. Dann gilt

a_i = a_i − 2 − q_i − 2 a_i − 1 =

n_i − 2 a + m_i − 2 b − q_i − 2 (n_i − 1 a + m_i − 1 b) =

(n_i − 2 − q_i − 2 n_i − 1) a + (m_i − 2 − q_i − 2 m_i − 1) b.

Nach (+) ist insbesondere d = a_i* + 1 eine Linearkombination von a und b.

Nach dem Beweis von (+) können wir für a > b > 0 also d = ggT(a, b) wie folgt effektiv als Linearkombination von a und b darstellen: Wir berechnen zuerst die Zahlen a_i und q_i für 0 < i ≤ i* des Euklidischen Algorithmus für a und b. Nun definieren wir rekursiv:

n₀ = 1, m₀ = 0, n₁ = 0, m₁ = 1,

n_i = n_i − 2 − q_i − 2 n_i − 1, m_i = m_i − 2 − q_i − 2 m_i − 1 für alle i mit 2 ≤ i ≤ i* + 1.

Dann gilt a_i = n_i a + m_i b für alle i mit 0 ≤ i ≤ i* + 1, und damit ist

d = n_i* + 1 a + m_i* + 1 b.

Die Darstellung des größten gemeinsamen Teilers ist keineswegs eindeutig. So ist etwa

1 = 1 · 3 − 1 · 2 = 3 · 3 − 4 · 2.

Wir halten weiter fest:

Korollar (Identifizierung der Linearkombinationen von a und b)

Die Linearkombinationen von a und b sind genau die Zahlen der Form kd, wobei d = ggT(a, b).

Insbesondere gilt: Sind a, b nicht beide gleich Null, so ist d die kleinste positive Linearkombination von a und b.

Beweis

Sei d = n a + m b. Dann ist kd = (kn) a + (km) b. Also sind alle Zahlen der Form kd Linearkombinationen von a und b.

Ist umgekehrt c = n′ a + m′ b eine Linearkombination von a und b, so ist d nach (T7) ein Teiler von c. Also existiert ein k mit c = kd.

Unsere Ergebnisse über Linearkombinationen lassen sich auch für einfache Beweise der Eigenschaften der ggT-Funktion nutzen. Wir betrachten noch einmal die wichtigen Eigenschaften:

(G6)	e\|a und e\|b impliziert e\|ggT(a, b),
(G7)	ggT(ca, cb) = \|c\| ggT(a, b),

die wir bei unserer Analyse des Euklidischen Algorithmus und der Linearkombinationen nicht verwendet haben.

Zum Beweis von (G6) sei d = ggT(a, b), und es sei

d = n a + m b.

Wegen e|a und e|b gilt dann e|d auch nach (T7).

Zum Beweis von (G7) sei wieder d = ggT(a, b) und d′ = ggT(ca, cb), und ohne Einschränkung sei c ≥ 0. Wegen cd|ca und cd|cb gilt cd ≤ d′. Zum Beweis der anderen Ungleichung sei d = na + mb. Dann ist dc = nac + mbc eine Linearkombination von ac und bc, und wegen dc ≥ 0 also dc ≥ d′ nach dem Korollar.

Eine direktere Möglichkeit, die Eigenschaft (G6) mit Hilfe des Euklidischen Algorithmus zu beweisen, ist die folgende. Es seien wieder a₀, …, a_i* + 1 die Zahlen, die der Euklidische Algorithmus für a > b > 0 erzeugt. Dann gilt:

(+) e|a_i für alle i mit 0 ≤ i ≤ i* + 1.

Damit gilt e|a_i* + 1 (und a_i* + 1 = d).

Wir können aber (+) leicht durch starke Induktion nach i zeigen:

Induktionsschritt i

Sei e ein Teiler von a_i′ für alle 0 ≤ i′ < i (Induktionsvoraussetzung).

Wegen e|a, e|b, a = a₀ und b = a₁ gilt die Behauptung für i = 0 und i = 1.

Ist i ≥ 2, so gilt a_i = a_i − 2 − q_i − 2 a_i − 1, und damit gilt e|a_i nach Induktionsvoraussetzung und (T7).

Damit können wir nun gut gerüstet den wohl faszinierendsten Objekten der Zahlentheorie begegnen, nämlich den Primzahlen.