Ein iteratives, divisionsbasiertes Verfahren zur Berechnung des größten gemeinsamen Teilers (ggT) zweier ganzer Zahlen, indem die größere Zahl wiederholt durch die kleinere geteilt und durch den Rest ersetzt wird, bis der Rest null ist; der letzte von null verschiedene Rest ist der ggT.

Prinzip

Sind a und b ganze Zahlen mit a = bq + r, dann gilt ggT(a,b) = ggT(b,r). Durch Wiederholung dieser Schrittfolge verringern sich die Operanden und die Terminierung ist garantiert; die erweiterte Form setzt Reste zurück ein, um Bézout-Koeffizienten zu liefern, die den ggT als ganze Linearkombination ausdrücken.

Demonstration

Berechne ggT(252, 198): 252 = 198·1 + 54, 198 = 54·3 + 36, 54 = 36·1 + 18, 36 = 18·2 + 0, also ggT = 18. Der erweiterte euklidische Algorithmus verfolgt Linearkombinationen, um x,y mit 252x + 198y = 18 zu finden.

Fehlanwendung

Gleitkommadivision ohne exakte Restkontrolle für ganze Zahlen zu verwenden oder Vorzeichen und Nullfälle nicht zu normalisieren; davon auszugehen, dass die naiven euklidischen Schritte die Komplexitätskosten für sehr große Zahlen vollständig erfassen, ohne den Kostenrahmen für ganzzahlige Arithmetik oder subquadratische Multiplikationsalgorithmen zu berücksichtigen.

Konsequenz

Bietet eine effiziente, terminierende Methode zur Berechnung von ggT, bildet die Grundlage für Berechnungen modularer Inversen, Vereinfachung rationaler Zahlen, Bestimmung von Ordnungen in der Kryptographie und Zahlentheorie und ist ein Baustein für Polynom-ggT in euklidischen Ringen.

Umkehrung

Im Gegensatz dazu stehen subtraktionsbasierte ggT-Algorithmen (wiederholte Subtraktion) oder der binäre ggT (Steins Algorithmus): diese erreichen denselben ggT mit anderen elementaren Operationen und können in bestimmten Hardware- oder Bit-Komplexitätsmodellen vorteilhafter sein.

Abgrenzung

Gilt in euklidischen Ringen, in denen ein Divisionsalgorithmus mit Rest existiert (Ganzenzahlen, univariate Polynome über einem Körper); er wendet sich nicht direkt auf allgemeine Ringe ohne euklidische Funktion an, und die Eingabe darf nicht der triviale Fall beider Nullen sein.

Semantische Spannung

Spannung zwischen dem klassischen schrittweisen euklidischen Algorithmus und modernen schnellen Implementierungen: in der Prinzip identisch, unterscheiden sie sich jedoch in der Komplexität beim Einsatz schneller ganzzahliger Arithmetik oder subresultanten/polynomiellen Varianten für multivariate Fälle.

Synthese

Der euklidische Algorithmus ist das grundlegende iterative Divisionsverfahren in euklidischen Ringen, das die ggT-Berechnung auf kleinere Reste reduziert, die Terminierung garantiert, in erweiterter Form Bézout-Darstellungen liefert und viele elementare Konstruktionen in der algorithmischen Zahlentheorie und Algebra begründet.