Der Euklidische Algorithmus

Der Euklidische Algorithmus ist ein effektives Verfahren zur Bestimmung des größten gemeinsamen Teilers d* zweier Zahlen a und b. Er gehört zu den ältesten, schönsten und fruchtbarsten Algorithmen der Mathematik. Das Verfahren wird uns nicht nur den größten gemeinsamen Teiler d* zweier Zahlen a und b liefern, sondern auch Koeffizienten n und m derart, dass

d* = n a + m b.

So ist zum Beispiel 3 = ggT(129, 33) und es gilt 3 = − 1 · 129 + 4 · 33.

Wegen ggT(a, b) = ggT(|a|, |b|) = ggT(|b|, |a|) genügt es, das Verfahren für Paare a, b mit a > b > 0 anzugeben. Es ist bestimmt durch die sog. Wechselwegnahme: In jedem Schritt des Algorithmus liegen zwei Zahlen vor (zu Beginn sind dies a und b). Wir ziehen nun die kleinere der beiden Zahlen von der größeren ab und erhalten so ein neues Zahlenpaar. Dies wiederholen wir so lange, bis beide Zahlen gleich sind. Wir werden zeigen, dass der so errechnete gemeinsame Wert des letzten Zahlenpaares nichts anderes ist als der größte gemeinsame Teiler des Ausgangspaares.

Wir verwenden folgende Fassung, bei der mehrere Schritte der gerade geschilderten Wechselwegnahme zu einem zusammengefasst werden.

Algorithmus von Euklid

Sei a > b > 0. Wir setzen a₀ = a, a₁ = b und berechnen nun schrittweise a₂, …, a_i, … durch Division mit Rest wie folgt:

a₀ = q₀ · a₁ + a₂	mit 0 < a₂ < a₁,
a₁ = q₁ · a₂ + a₃	mit 0 < a₃ < a₂,

…

a_i = q_i · a_i + 1 + a_i + 2

mit 0 < a_i + 2 < a_i + 1,

…

Wir beenden das Verfahren mit a_i* + 1 als Ergebnis, sobald wir einen Index i* gefunden haben mit a_i* = q_i* · a_i* + 1. Wir setzen dann noch a_i* + 2 = 0.

Das Verfahren muss nach endlich vielen Schritten abbrechen und ein Ergebnis a_i* + 1 liefern, da nach Konstruktion a₀ > a₁ > … > a_i > … > 0 gilt.

Der Algorithmus ist ein Beispiel für eine (nach endlich vielen Schritten abbrechende) rekursive Definition von Zahlen a_i. Im Rekursionsanfang setzen wir a₀ = a und a₁ = b. Im Rekursionsschritt wird a_i + 2 mit Rückgriff auf a_i und a_i + 1 definiert durch die eindeutige Darstellung

a_i = q_i · a_i + 1 + a_i + 2, 0 ≤ a_i + 2 < a_i + 1.

Sobald a_i + 2 = 0 ist, wird die Rekursion abgebrochen.

Der Algorithmus verläuft für das obige Paar a = a₀ = 129 und b = a₁ = 33 wie folgt:

129	= 3 · 33 + 30,	q₀ = 3, a₂ = 30,
33	= 1 · 30 + 3,	q₁ = 1, a₃ = 3,
30	= 10 · 3,	q₂ = 10.

Das Ergebnis der Berechnung ist also 3. Zurückrechnen liefert nun:

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

Damit haben wir obige Darstellung von 3 = ggT(129, 33) gefunden.

Dass der Algorithmus in der Tat das leistet, was wir von ihm behaupten, wollen wir nun beweisen.

Satz (Korrektheit des Euklidischen Algorithmus)

Sei d* das Ergebnis des Euklidischen Algorithmus für a > b > 0.

Dann gilt d* = ggT(a, b).

Beweis

Seien a₀ > a₁ > a₂ > … > a_i* + 1 = d* und q₀, …, q_i* die Zahlen, die der Euklidische Algorithmus für a = a₀ und b = a₁ liefert. Sei d = ggT(a, b).

Wir zeigen durch Induktion nach i:

(+) d = ggT(a_i, a_i + 1) für alle i mit 0 ≤ i ≤ i*.

Induktionsanfang i = 0

Es gilt ggT(a₀, a₁) = ggT(a, b) = d.

Induktionsschritt von i nach i + 1

Es gelte also d = ggT(a_i, a_i + 1) (Induktionsvoraussetzung).

Dann gilt

ggT(a_i + 1, a_i + 2) = ggT(a_i + 1, a_i − q_i a_i + 1) =_(G5) ggT(a_i + 1, a_i) =_(G2) d.

Damit haben wir aber:

d =_{(+) für i = i*} ggT(a_i*, a_i* + 1) = ggT(q_i* a_i* + 1, a_i* + 1) = ggT(q_i* d*, d*) = d*.

Der Leser sieht, dass die Korrektheit des Euklidischen Algorithmus letztendlich auf der einfachen Eigenschaft (G5) ruht. In der oben geschilderten Fassung der Wechselwegnahme wird dies besonders deutlich: Ist a′, b′ das aktuell vorliegende Paar mit a′ ≠ b′, so ist a′ − b′, b′ oder a′, b′ − a′ das nächste Paar, je nachdem, ob b′ < a′ oder a′ < b′ gilt. Da aber

ggT(a′, b′) = ggT(a′ − b′, b′) = ggT(a′, b′ − a′)

gilt, bewahrt die Wechselwegnahme in jedem Schritt den größten gemeinsamen Teiler des Ausgangspaares a, b.