Ein iteratives, auf Division basierendes Verfahren, das den größten gemeinsamen Teiler (ggT) zweier Elemente in einem euklidischen Bereich (oder einem Ring mit geeigneter euklidischer Bewertung) durch wiederholte Restberechnung bis zum Abbruch bei Null ermittelt.

Prinzip

Verwendung der Division mit Rest, um eine streng abnehmende Folge von euklidischen Normen zu erzeugen; die Terminierung liefert den letzten von null verschiedenen Rest als ggT, und Rücksubstitution ergibt Bézout-Koeffizienten, wenn anwendbar.

Demonstration

Ganzzahliges Beispiel: ggT(1071,462). Rechenschritte: 1071 = 462·2 + 147, 462 = 147·3 + 21, 147 = 21·7 + 0; der letzte von null verschiedene Rest ist 21, also ggT(1071,462)=21. Der erweiterte Algorithmus liefert x,y mit 1071x+462y=21.

Fehlanwendung

Den einfachen Division-Algorithmus in Ringen ohne euklidische Bewertung anwenden oder annehmen, der Algorithmus liefere eindeutige ggT in Ringen ohne geeignete Norm; auch die Terminierung ohne Nachweis einer streng abnehmenden Messgröße voraussetzen.

Konsequenz

Bietet ein effektives Verfahren zur Berechnung von ggT, zur Bestimmung der Invertierbarkeit modulo eines Elements und zur Herstellung von Bézout-Darstellungen mittels des erweiterten Algorithmus; Grundlage für modulare Inverse und viele algorithmische Methoden der Zahlentheorie.

Umkehrung

Anstatt durch Reste zu reduzieren, kann man einen ggT durch Faktorisierung beider Elemente und Schnittmengenbildung der Faktormultimengen synthetisieren; diese Umkehr vertauscht iterative Reduktion gegen globale Faktoranalyse.

Abgrenzung

Gilt in euklidischen Bereichen (z. B. Z, F[x]) oder in Umgebungen mit euklidischer Bewertung; schließt allgemeine Ringe ohne Divisionsalgorithmus oder wohlfundierte Norm aus und erfordert Anpassungen (Pseudo-Division) über allgemeinen Koeffizientenringen.

Semantische Spannung

Wird manchmal mit allgemeineren ggT-Konstruktionen (idealtheoretischer ggT, Subresultant-Verfahren) oder mit erweiterten vs. klassischen Varianten verwechselt; Spannung besteht zwischen Einsatz für exakte algebraische ggT und numerischen Approximationen.

Synthese

Der euklidische Algorithmus ist das Verfahren wiederholter Divisionen mit Rest gesteuert durch eine euklidische Bewertung; er terminiert endlich und liefert den ggT und durch Rücksubstitution Bézout-Koeffizienten, sofern der Bereich dies gestattet.