Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler $\backslash operatorname\{ggT\}(a,b)$ zweier natürlicher Zahlen $a$ und $b$ noch zwei ganze Zahlen $s$ und $t$, die die folgende Gleichung erfüllen

$\backslash operatorname\{ggT\}(a,b)\; =\; s\; \backslash cdot\; a\; +\; t\; \backslash cdot\; b$

Wie der Name schon aussagt ist dieser Algorithmus eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus, der nur den größten gemeinsamen Teiler berechnet.

Das Haupteinsatzgebiet des erweiterten euklidischen Algorithmus ist die Berechnung der inversen Elemente in primen Restklassengruppen. Der Algorithmus liefert zudem einen konstruktiven Beweis für das Lemma von Bézout.

Funktionsweise

---

Zur Berechnung werden die Variablen m, n, s, t, u und v verwendet. Diese werden wie folgt initialisiert:

• Setze m = a, n = b, s = 1, t = 0, u = 0, v = 1

• Wiederhole solange n ≠ 0

1. Berechne q und r mit m = q * n + r (Division mit Rest)
2. Setze m = n, n = r, u' = s - q * u, v' = t - q * v
3. Setze s = u, t = v, u = u', v = v'

Nach Beendigung ist $\backslash operatorname\{ggT\}(a,b)=\; m\; =\; s\backslash cdot\; a\; +\; t\backslash cdot\; b$.

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

$\backslash 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} Dabei ist q der ganzzahlige Anteil von m/n.

Man zieht also immer von der vorletzten Zeile die mit q multiplizierte letzte Zeile ab, um die nächste Zeile zu erhalten. Wenn die Abbruchbedingung n=0 erfüllt ist, gilt m = r = ggT(a,b) und folglich

$\backslash operatorname\{ggT\}(a,b)\; =\; s\backslash cdot\; a\; +\; t\backslash cdot\; b.$

Rekursive Variante

Für den erweiterte euklidische Algorithmus existiert auch eine rekursive Variante, die durch den folgenden Pseudocode gegeben ist:Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 2001, ISBN 0262531968 a,b: zwei Zahlen für die der erweiterte euklidische Algorithmus durchgeführt wird extended_euclid(a,b) 1 wenn b = 0 2 dann return (a,1,0) 3 (d',s',t') $\backslash leftarrow$ extended_euclid(b, a mod b) 4 (d,s,t) $\backslash leftarrow$ (d',t',s' - floor(a/b)t') 5 return (d,s,t)

Quellen

---

Weblinks

---

Umfangreiche Arbeit u.a. zum euklidischen Algorithmus

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 ^*.

Algorithmus | Zahlentheorie

Extended Euclidean algorithm | Algorithme d'Euclide étendu | Uitgebreid Euclidisch algoritme