Der Euklidische Algorithmus
Die Bestimmung des größen gemeinsamen Teilers über die Primfaktorzerlegung ist theoretisch elegant, aber praktisch oft nur schwer durchführbar, da die Primfaktorzerlegung in der Regel sehr aufwendig zu berechnen ist. Ein effektives und mathematisch zudem sehr schönes und gehaltvolles Verfahren zur Berechnung des größten gemeinsamen Teilers ist:
Euklidischer Algorithmus, Version I: einfache Wechselwegnahme
Seien a, b > 0. Wir ziehen wiederholt die kleinere Zahl von der größeren Zahl ab. Wir stoppen mit Ergebnis g ≥ 1, wenn beide Zahlen durch diese Wegnahme gleich g geworden sind.
Beispiel
Für 48 und 15 liefert das Verfahren die Folge von Zahlenpaaren:
| 48, 15 | 33, 15 | 18, 15 | 3, 15 |
| 3, 12 | 3, 9 | 3, 6 | 3, 3 |
Das Ergebnis der Berechnung ist g = 3.
Wie bei jedem Algorithmus müssen wir uns überlegen, ob und gegebenenfalls für welche Startwerte das Verfahren terminiert, d. h. ein Ergebnis erzeugt. Für den Euklidischen Algorithmus ist dies einfach: In jedem Schritt wird eine der beiden Zahlen kleiner. Da es in den natürlichen Zahlen keine unendlichen strikt absteigenden Folgen gibt, muss das Verfahren für beliebig große Startwerte nach endlich vielen Schritten abbrechen.
Weiter müssen wir zeigen, dass das Verfahren leistet, was wir von ihm erwarten. Wir formulieren und beweisen:
Satz (Korrektheit des Euklidischen Algorithmus)
Der Euklidische Algorithmus liefert für alle a, b > 0 den größten gemeinsamen Teiler g = ggT(a, b) der beiden Zahlen.
Beweis
Seien a, b > 0. Nach der Eigenschaft (G5) bleibt der größte gemeinsame Teiler beim Übergang von
a, b zu a, b − a bzw. a, b zu a − b, b
erhalten. Induktiv folgt, dass alle durch die Berechnung erzeugten Zahlenpaare denselben ggT besitzen. Damit gilt insbesondere
(a, b) = (g, g) = g.
Der Leser wird bei der Betrachtung des obigen Beispiels festgestellt haben, dass die 15 dreimal in die 48 und die 3 fünfmal in die 15 hineinpasst. Er wird sich vielleicht gefragt haben, warum wir wiederholten Subtraktionen nicht zusammengefasst haben. Die Antwort ist: „Ziehe die kleinere von der größeren Größe ab.“ ist die einfachste Formulierung des Verfahrens bringt seine Idee vielleicht am besten zur Geltung. Natürlich lassen sich wiederholte Wegnahmen auf der gleichen Seite bündeln. Dieses Vorgehen entspricht einer wiederholten Division mit Rest und führt zu folgender Version des Verfahrens:
Euklidischer Algorithmus, Version II: Division mit Rest
Seien a > b > 0. Wir setzen a0 = a, a1 = b und definieren mit Hilfe von Division mit Rest Zahlen a2 > … > an + 1 > 0 und Vielfachheitsquotienten q0, …, qn durch
| a0 | = q0 a1 + a2 | 0 < a2 < a1 |
| a1 | = q1 a2 + a3 | 0 < a3 < a2 |
| a2 | = q2 a3 + a4 | 0 < a4 < a3 |
| … | ||
| an | = qn an + 1 |
Wir beenden das Verfahren mit Ergebnis an + 1.
Der Leser beachte, dass in jedem Schritt der letzte Quotient zur neuen zu dividierenden Zahl und der letzte Rest zum neuen Quotienten wird.
Die zweite Version unterscheidet sich von der ersten im Wesentlichen dadurch, dass mehrere Schritte zu einem Schritt zusammengefasst werden. Damit ist das Ergebnis der Berechnung erneut der ggT der beiden Anfangszahlen, d. h. es gilt an + 1 = ggT(a, b).
Beispiel
Angewendet auf a = a0 = 129 und b = a1 = 33 erhalten wir:
| 129 | = 3 · 33 + 30 | q0 = 3 | a2 = 30 |
| 33 | = 1 · 30 + 3 | q1 = 1 | a3 = 3 |
| 30 | = 10 · 3 | q2 = 10 |
Damit ist (a, b) = (129, 33) = a3 = 3.
Der Euklidischen Algorithmus lässt sich mit Hilfe von Rechtecksflächen visualisieren: Von einem Rechteck werden solange Quadrate abgetrennt, bis ein Quadrat entsteht. Die Seitenlänge dieses Quadrats ist der größte gemeinsame Teiler der Rechtsecksseiten. In den folgenden Diagrammen ändern wir die Farbe der entfernten Quadrate bei jedem kleiner-größer-Wechsel der Seitenlängen, sodass die Folge der Vielfachheitsquotienten sichtbar wird.
ggT(39, 12) = 3, Quotientenfolge: 3, 4
ggT(36, 14) = 2, Quotientenfolge: 2, 1, 1, 3
ggT(34, 21) = 1, Quotientenfolge: 1, 1, 1, 1, 1, 1, 2
ggT(153, 112) = 1, Quotientenfolge: 1, 2, 1, 2, 1, 2, 1, 2