Der erweiterte Euklidische Algorithmus berechnet aus den Zahlen a und b nicht nur den ggT sondern auch die Zahlen s und t, für die gilt:
ggT(a, b) = s * a + t * b
Der erweiterte Euklidische Algorithmus wird wie folgt durchgeführt:
Moderner Euklidischer Algorithmus in den Spalten a, b, q und r
Dann wird in der letzte Zeile s = 0 und t = 1 gesetzt
sneu = talt und tneu = salt - qneu * talt
Berechne den ggT(, )
Wenn der ggT(a, b) = 1, dann gilt (s * a) mod b = 1 und (t * b) mod a = 1.