de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Erweiterter euklidischer Algorithmus
Nachlesen

Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem Gebiet der Zahlentheorie, mit dem sich neben dem größten gemeinsamen Teiler zweier natürlicher Zahlen \(a\) und \(b\) außerdem zwei ganze Zahlen \(s\) und \(t\) berechnen lassen, für die die nachfolgende Gleichung gilt:

\[ \ggT(a,b) = s \cdot a + t \cdot b. \]

Es handelt sich um eine Erweiterung des euklidischen Algorithmus.

Inhalt

Beschreibung des Verfahrens

Gegeben seien zwei natürliche Zahlen \(a\) und \(b\) mit \(b \leq a\), für die zunächst der größte gemeinsame Teiler \(\ggT(a,b)\) mithilfe des euklidischen Algorithmus bestimmt wird. Dieser liefert die nachfolgenden Zerlegungen mit Rest. Wie üblich kann der größte gemeinsame Teiler \(\ggT(a,b) = r_n\) an der vorletzten Zeile abgelesen werden.

\begin{align*} a &= q_1 \cdot b + r_1 \\[0.5em] b &= q_2 \cdot r_1 + r_2 \\[0.5em] &\ \ \vdots \\[0.5em] r_{n-3} &= q_{n-1} \cdot r_{n-2} + r_{n-1} \\[0.5em] r_{n-2} &= q_n \cdot r_{n-1} + r_n \\[0.5em] r_{n-1} &= q_{n+1} \cdot r_n + 0 \end{align*}

Zum Bestimmen der gesuchten ganzen Zahlen \(s\) und \(t\) wird nun zunächst die vorletzte Gleichung nach \(r_n\) umgestellt.

\[ r_n = r_{n-2} - q_n \cdot r_{n-1} \]

Anschließend wird der Wert \(r_{n-1}\) mit der nach \(r_{n-1}\) umgestellten vorvorletzten Gleichung ersetzt und die erhaltene Gleichung zusammengefasst.

\begin{align*} r_n &= r_{n-2} - q_n \cdot r_{n-1} \\[0.5em] &= r_{n-2} - q_n \cdot \bigl( r_{n-3} - q_{n-1} \cdot r_{n-2} \bigr) \\[0.5em] &= -q_n \cdot r_{n-3} + \bigl( 1 + q_n \cdot q_{n-1} \bigr) \cdot r_{n-2} \end{align*}

Im nächsten Schritt wird nun nach demselben Prinzip der Wert \(r_{n-2}\) ersetzt. Dies wird analog für die Werte \(r_{n-3}, \ldots, r_1\) wiederholt. Nachdem im letzten Schritt schließlich der Wert \(r_1\) ersetzt wurde, ergibt sich eine Gleichung der Form

\[ \ggT(a,b) = r_n = \underbrace{\bigl( \ldots \bigr)}_{=s} \cdot a + \underbrace{\bigl( \ldots \bigr)}_{=t} \cdot b, \]

an der die gesuchten ganzen Zahlen \(s\) und \(t\) direkt abgelesen werden können.

Beispiel

Es sollen ganze Zahlen \(s\) und \(t\) bestimmt werden, so dass gilt:

\[ \ggT(42,23) = s \cdot 42 + t \cdot 23. \]

Zunächst wird mit dem euklidischen Algorithmus der größte gemeinsame Teiler von \(42\) und \(23\) bestimmt. Dieser kann wie üblich an der vorletzten Zeile abgelesen werden.

\begin{align*} 42 &= 1 \cdot 23 + {\color{LimeGreen} 19} \\[0.5em] 23 &= 1 \cdot 19 + {\color{Magenta} 4} \\[0.5em] 19 &= 4 \cdot 4 + {\color{Orange} 3} \\[0.5em] 4 &= 1 \cdot 3 + {\color{CornflowerBlue} 1} \\[0.5em] 3 &= 3 \cdot 1 + 0 \end{align*}

Zum Bestimmen der gesuchten Werte \(s\) und \(t\) wird zunächst die vorletzte Gleichung nach dem größten gemeinsamen Teiler \({\color{CornflowerBlue} 1}\) umgestellt. Der in der so erhaltenen Gleichung vorkommende Wert \({\color{Orange} 3}\) (der Rest der darüberliegenden Gleichung im euklidischen Algorithmus) wird im Anschluss durch die nach diesem Wert umgestellten darüberliegenden Gleichung ersetzt. Dies wird für alle Gleichungen wiederholt, so dass schrittweise ebenfalls die Reste \({\color{Magenta} 4}\) und \({\color{LimeGreen} 19}\) ersetzt werden.

\begin{align*} 1 &= 1 \cdot 4 - 1 \cdot {\color{Orange} 3} \\[0.5em] &= 1 \cdot 4 - 1 \cdot {\color{Orange} \bigl( 19 - 4 \cdot 4 \bigr)} \\[0.5em] &= -1 \cdot 19 + 5 \cdot {\color{Magenta} 4} \\[0.5em] &= -1 \cdot 19 + 5 \cdot {\color{Magenta} \bigl( 23 - 1 \cdot 19 \bigr)} \\[0.5em] &= 5 \cdot 23 - 6 \cdot {\color{LimeGreen} 19} \\[0.5em] &= 5 \cdot 23 - 6 \cdot {\color{LimeGreen} \bigl( 42 - 1 \cdot 23 \bigr)} \\[0.5em] &= -6 \cdot 42 + 11 \cdot 23 \end{align*}

An der resultierenden Gleichung

\[ \ggT(42,23) = 1 = \underbrace{-6}_{=s} \cdot 42 + \underbrace{11}_{=t} \cdot 23 \]

können die gesuchten ganzzahligen Werte \(s=-6\) und \(t=11\) direkt abgelesen werden.