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 ganzen 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 s gerade das multiplikative Inverse von a modulo b.
Funktionsweise
Der Algorithmus sieht wie folgt aus:
- Setze m=a, n=b, s=1, t=0, u=0, v=1
- Berechne q und r mit m = q*n + r (Division mit Rest)
- Setze m=n, n=r, u'=s-q*u, v'=t-q*v
- Setze s = u, t = v, u=u', v=v'
- Falls n ≠ 0 gehe zu Schritt 2.
Nach Beendigung ist ggT(a,b)=m=sa+tb.
