Ein iteratives Divisionverfahren zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier ganzer Zahlen, indem man wiederholt die größere Zahl durch den Rest bei Division durch die kleinere ersetzt, bis der Rest null ist.

Prinzip

ggT(a,b) = ggT(b, a mod b); wiederholte Anwendung dieser Reduktion verringert die Größe der Operanden und endet mit dem ggT, sobald ein Rest Null wird.

Demonstration

Berechnung von ggT(48, 18): 48 = 2·18 + 12, 18 = 1·12 + 6, 12 = 2·6 + 0, also ggT(48,18) = 6. Der erweiterte Algorithmus liefert Koeffizienten x,y mit 48x + 18y = 6.

Fehlanwendung

Das Anwenden des Algorithmus auf Nicht-Ganzzahlen ohne euklidische Divisionsstruktur oder die Annahme konstanter Laufzeit unabhängig von Operandenlängen sind typische Fehlanwendungen; ebenso muss man mit negativen oder Null-Eingaben korrekt umgehen.

Konsequenz

Der euklidische Algorithmus bietet eine effiziente Methode zur Berechnung des ggT, bildet die Grundlage zur Berechnung modularer Inversen und Bezout-Koeffizienten (erweiterter Algorithmus) und verallgemeinert auf euklidische Ringe.

Umkehrung

Die Verwendung der Primfaktorzerlegung zur Bestimmung des ggT ist der konzeptuelle Gegenansatz; Faktorisierung liefert zwar den ggT, ist aber bei großen Zahlen meist deutlich ineffizienter als die euklidische Reduktion.

Abgrenzung

Gilt für ganze Zahlen und für jeden euklidischen Ring mit einer Divisionsalgorithmus mit Rest; er gilt nicht direkt für beliebige Ringe ohne euklidische Norm oder für Objekte ohne wohldefinierte Restoperation.

Semantische Spannung

Gegenüberstellung des euklidischen Algorithmus mit binären ggT-Algorithmen und faktorisierungsbasierten Methoden: Euclid reduziert mittels Division mit Rest, binäre Algorithmen nutzen binäre Operationen, Faktorisierung stützt sich auf Primfaktoren.

Synthese

Der euklidische Algorithmus reduziert ein ggT-Problem durch sukzessive Restdivisionen bis zum Abschluss und bietet eine effiziente, verallgemeinerbare Prozedur, die zugleich lineare Kombinationen ergibt, welche den ggT ausdrücken.