Erweiterter Euklidischer Algorithmus
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.
