Ein Algorithmus, der den größten gemeinsamen Teiler (ggT) zweier ganzer Zahlen berechnet und gleichzeitig ganze Koeffizienten u und v liefert, sodass u·a + v·b = ggT(a,b). Es ist der euklidische Algorithmus erweitert um die Bézout‑Koeffizienten.

Prinzip

Wiederholte Division mit Rest wird angewandt, bis ein Nullrest auftritt; durch Rücksubstitution der Divisionen drückt man den letzten nicht‑null Rest als Linearkombination der Ausgangszahlen aus.

Demonstration

Für ggT(99,78): 99 = 78·1 + 21, 78 = 21·3 + 15, 21 = 15·1 + 6, 15 = 6·2 + 3, 6 = 3·2 + 0, daher ggT = 3. Rücksubstitution liefert 3 = 78·14 + 99·(−11), also erfüllen u = −11 und v = 14 −11·99 + 14·78 = 3.

Fehlanwendung

Den ganzzahligen Algorithmus ungeprüft auf Fließkommazahlen oder in nicht‑euklidischen Ringen zu verwenden; die erhaltenen Koeffizienten als eindeutig anzusehen, ohne ihre Mehrdeutigkeit modulo gemeinsamer Faktoren zu berücksichtigen.

Konsequenz

Richtig angewandt ergibt er ggT und Bézout‑Koeffizienten, was Lösungen linearer diofantischer Gleichungen, Berechnung modularer Inversen und zahlreiche Anwendungen in der algorithmischen Zahlentheorie ermöglicht.

Umkehrung

Die Umkehr wäre, aus den Bézout‑Koeffizienten eine Faktorisierung der Eingaben abzuleiten; Koeffizienten geben nur lineare Relationen und ersetzen nicht eine Faktorisierungsmethode.

Abgrenzung

Definiert für Paare in Hauptidealbereichen und euklidischen Ringen (z. B. ganze Zahlen, univariate Polynome über einem Körper). Ohne Anpassung nicht direkt auf beliebige nicht‑euklidische Ringe oder multivariate Polynome anwendbar.

Semantische Spannung

Unterscheidet sich vom einfachen euklidischen Algorithmus, der nur den ggT liefert; das 'erweiterte' Merkmal liefert explizit Linearkombinationen, was leicht mit anderen Inversionsverfahren in multiplikativen Gruppen verwechselt wird.

Synthese

Der erweiterte euklidische Algorithmus erweitert die ggT‑Prozedur um systematische Rücksubstitution, um Bézout‑Koeffizienten zu liefern und so ggT sowie die zugehörige lineare Kombination bereitzustellen.