Der erweiterte euklidische Algorithmus ist, wie der Name schon sagt, eine Erweiterung des euklidischen Algorithmus. Die Eingabe besteht aus zwei Zahlen a und b und der Algorithmus liefert den größten gemeinsamen Teiler d sowie zwei ganze Zahlen s und t mit d = sa+tb.

Die Darstellung d = sa+tb ist besonders nützlich, wenn a und b teilerfremd sind. In diesem Fall ist d=1 und s ist das multiplikative Inverse von a modulo b.

Funktionsweise

Der Algorithmus sieht wie folgt aus:

1. Setze m=a, n=b, s=1, t=0, u=0, v=1
2. Berechne q und r mit m = q*n + r (Division mit Rest)
3. Setze m=n, n=r, u'=s-q*u, v'=t-q*v
4. Setze s = u, t = v, u=u', v=v'
5. Falls n ? 0 gehe zu Schritt 2.

Nach Beendigung ist ggT(a,b)=m=sa+tb.