Erweiterter Euklidischer Algorithmus

Eine Variante des euklidischen Algorithmus, die für zwei ganze Zahlen a und b ihren größten gemeinsamen Teiler g berechnet und zusätzlich ganze Zahlen x und y liefert, so dass ax + by = g (Bézout-Koeffizienten).

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.