Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist 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 (Lemma von Bézout).

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

Vorgehen

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.

Man kann dieses Vorgehen in der folgenden Form übersichtlich darstellen:

${\begin{matrix}a&=&1\cdot a&+&0\cdot b\\b&=&0\cdot a&+&1\cdot b\\\vdots &&\vdots &&\vdots \\m&=&s\cdot a&+&t\cdot b\\n&=&u\cdot a&+&v\cdot b\\r=m-qn&=&(s-qu)\cdot a&+&(t-qv)\cdot b\end{matrix}}$

Man zieht immer von der vorletzten Zeile ein geeignetes Vielfaches der letzten Zeile ab, um die nächste Zeile zu erhalten. Auf der linken Seite der Gleichungen wird der gewöhnliche euklidische Algorithmus durchgeführt, also erhält man schließlich eine Darstellung

$\mathrm {ggT} (a,b)=x\cdot a+y\cdot b.$

Beziehung zu Kettenbrüchen

Die Folge der auftretenden Zahlen $q$ liefert die Kettenbruchdarstellung von $a/b$: Z.B. ergibt sich für $a=37$ und $b=16$:

${\begin{matrix}37&=&1\cdot 37&+&0\cdot 16\\16&=&0\cdot 37&+&1\cdot 16;&q=2\\5&=&1\cdot 37&-&2\cdot 16;&q=3\\1&=&(-3)\cdot 37&+&6\cdot 16;&q=5\\0&=&16\cdot 37&-&37\cdot 16\end{matrix}}$

Also ist $\operatorname {ggT} (37,16)=1=(-3)\cdot 37+6\cdot 16$ und

${\frac {37}{16}}=2+{\frac {1}{3+{\frac {1}{5}}}}.$

Weblinks

Ein kleines Script findet sich unter http://www.mirsky.de/ggt.php. Jeder Schritt wird genau erklärt. Außerdem gibt es noch ein ausführliches Skript mit Quelltext unter [1].