Erweiterter Euklidischer Algorithmus

Studium

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

Voraussetzung: $a, b \in \mathbb{Z},$ $(a, b) \neq (0, 0),$ $s, t \in \mathbb{Z}$

$a, b$: ganze Zahlen, nicht beide null
$\operatorname{ggT}(a, b)$: größter gemeinsamer Teiler von a und b
$s, t$: ganzzahlige Bézout-Koeffizienten, die der erweiterte Algorithmus liefert

Der ggT zweier Zahlen lässt sich als ganzzahlige Kombination s·a + t·b schreiben; s und t liefert der erweiterte Algorithmus.

Erklärung

Das Lemma von Bézout sagt: Zu ganzen Zahlen $a, b$ , nicht beide null, gibt es ganze Zahlen $s, t$ mit $\operatorname{ggT}(a, b) = s \cdot a + t \cdot b$ . Der erweiterte Euklidische Algorithmus berechnet $s$ und $t$ gleich mit.

Vorgehen:

Den gewöhnlichen Euklidischen Algorithmus durchführen und alle Divisionen $r_{k-1} = q_k \cdot r_k + r_{k+1}$ notieren.
Die vorletzte Gleichung nach dem ggT auflösen.
Von unten nach oben die Reste nacheinander durch die darüberliegenden Gleichungen ersetzen, bis nur noch $a$ und $b$ vorkommen.

Die Koeffizienten sind nicht eindeutig: Mit $d = \operatorname{ggT}(a, b)$ ist auch $\left(s + k \cdot \frac{b}{d}\right) a + \left(t - k \cdot \frac{a}{d}\right) b = d$ für jedes ganze $k$ .

Wichtigste Anwendung ist das modulare Inverse: Ist $\operatorname{ggT}(a, m) = 1$ , dann folgt aus $1 = s \cdot a + t \cdot m$ , dass $s \cdot a \equiv 1 \pmod m$ . Also ist $s$ (auf $0, \ldots, m-1$ reduziert) das Inverse von $a$ modulo $m$ . Das braucht man beim Chinesischen Restsatz und bei RSA.

Beispiele

$\operatorname{ggT}(240, 46)$ als Kombination. Divisionen:

\begin{aligned} 240 &= 5 \cdot 46 + 10 \\ 46 &= 4 \cdot 10 + 6 \\ 10 &= 1 \cdot 6 + 4 \\ 6 &= 1 \cdot 4 + 2 \\ 4 &= 2 \cdot 2 + 0 \end{aligned}

Also $\operatorname{ggT}(240, 46) = 2$ . Rückwärts einsetzen:

\begin{aligned} 2 &= 6 - 4 = 6 - (10 - 6) = 2 \cdot 6 - 10 \\ &= 2 \cdot (46 - 4 \cdot 10) - 10 = 2 \cdot 46 - 9 \cdot 10 \\ &= 2 \cdot 46 - 9 \cdot (240 - 5 \cdot 46) = -9 \cdot 240 + 47 \cdot 46 \end{aligned}

Ergebnis: $s = -9$ , $t = 47$ . Mit $k = 1$ erhält man eine weitere Lösung: $14 \cdot 240 - 73 \cdot 46 = 2$ .

Inverses von $7$ modulo $26$ : $26 = 3 \cdot 7 + 5$ , $7 = 1 \cdot 5 + 2$ , $5 = 2 \cdot 2 + 1$ . Rückwärts:

1 = 5 - 2 \cdot 2 = 5 - 2 \cdot (7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7

Also $-11 \cdot 7 \equiv 1 \pmod{26}$ . Das Inverse ist $-11 + 26 = 15$ . Probe: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ .

Typische Fehler

Vorzeichenfehler beim Einsetzen. Beim Ersetzen eines Rests muss die ganze Klammer mit dem Koeffizienten multipliziert werden: $-(10 - 6) = -10 + 6$ . Am Ende immer die Probe $s \cdot a + t \cdot b$ rechnen.
Negatives Inverses stehen lassen. $-11$ ist zwar ein Inverses von $7$ modulo $26$ , üblich ist aber der Vertreter $15$ zwischen $0$ und $25$ .
Ein Inverses suchen, wo keines existiert. Modulo $m$ ist $a$ nur invertierbar, wenn $\operatorname{ggT}(a, m) = 1$ . Wegen $\operatorname{ggT}(240, 46) = 2$ hat $46$ modulo $240$ kein Inverses.
$s$ und $t$ für eindeutig halten. Es gibt unendlich viele Paare; zwei verschiedene Ergebnisse können beide richtig sein.

Erweiterter Euklidischer Algorithmus