imported>Rigormath: /* Funktionsweise der iterativen Variante */ Link zu Divison mit Rest.

2026-04-18T15:46:47Z

Funktionsweise der iterativen Variante: Link zu Divison mit Rest.

Neue Seite

Der '''erweiterte euklidische Algorithmus''' ist ein [[Algorithmus]] aus dem [[Teilgebiete der Mathematik|mathematischen Teilgebiet]] der [[Zahlentheorie]]. Er berechnet neben dem [[größter gemeinsamer Teiler|größten gemeinsamen Teiler]] <math>\operatorname{ggT}(a,b)</math> zweier [[Natürliche Zahl|natürlicher Zahlen]] <math>a</math> und <math>b</math> noch zwei [[ganze Zahlen]] <math>s</math> und <math>t</math>, die die folgende Gleichung erfüllen:

:<math>\operatorname{ggT}(a,b) = s \cdot a + t \cdot b</math>

Der Algorithmus ist eine Erweiterung des bereits in der [[Antike]] bekannten [[Euklidischer Algorithmus|euklidischen Algorithmus]], der nur den größten gemeinsamen Teiler berechnet.

Das Haupteinsatzgebiet des erweiterten euklidischen Algorithmus ist die [[Restklassenring#Invertierbarkeit und Inversenberechnung|Berechnung der inversen Elemente]] in [[Prime Restklassengruppe|ganzzahligen Restklassenringen]], denn wenn der Algorithmus das Tripel <math>(d=\operatorname{ggT}(a,b), s, t)</math> ermittelt, ist entweder <math>d=1</math> und damit <math>1\equiv t\cdot b \pmod a</math>, <math>t</math> also das multiplikative Inverse von <math>b</math> modulo <math>a,</math> oder aber <math>d\neq 1,</math> was bedeutet, dass <math>b</math> modulo <math>a</math> kein Inverses hat.
Dies ist die Grundlage für die Lösung von [[Lineare Diophantische Gleichung|diophantischen Gleichungen]] oder allgemeiner von ganzzahligen [[Lineares Gleichungssystem|linearen Gleichungssystemen]]. Ebenso ist die Bestimmung inverser Elemente eine Grundlage für den [[Chinesischer Restsatz|chinesischen Restsatz]], welcher wiederum Grundlage des bedeutenden Tricks der kleinen Primzahlen in der berechenbaren Algebra ist. Dabei wird eine Aufgabe in mehreren [[Endlicher Körper|endlichen Körpern]] gelöst und diese Teillösungen in immer größere Restklassenringe gehoben, bis sich eine ganzzahlige Lösung ablesen lässt. Der Algorithmus liefert zudem einen [[Konstruktiver Beweis|konstruktiven Beweis]] für das [[Lemma von Bézout]], also <math>1 = s \cdot a + t \cdot b</math>.

Die am weitesten bekannte Version des euklidischen Algorithmus bezieht sich auf den Bereich der ganzen Zahlen. Jedoch kann er auf jeden [[Ring (Algebra)|Ring]] angewandt werden, in welchem eine Division mit kleinstem Rest durchgeführt werden kann. Solche Ringe werden [[Euklidischer Ring|euklidisch]] genannt, ein Beispiel ist der [[Polynomring]] in einer Variablen mit rationalen oder reellen Koeffizienten. In diesem kann immer ein eindeutig bestimmter Rest mit kleinstem Grad gefunden werden.

== Funktionsweise der iterativen Variante ==

Die iterative Variante des EEA berechnet aus den vorgegebenen <math>a,b</math> drei Zahlenfolgen <math>r_i, s_i, t_i</math>. Diese werden zunächst initialisiert:
:<math>r_0 = a,\quad r_1 = b</math>
:<math>s_0 = 1,\quad s_1 = 0</math>
:<math>t_0 = 0,\quad t_1 = 1</math>
Dann wird für <math>i = 1,2,\ldots</math> berechnet:
:<math>r_{i+1} = r_{i-1} - q_i \cdot r_i</math>
:<math>s_{i+1} = s_{i-1} - q_i \cdot s_i</math>
:<math>t_{i+1} = t_{i-1} - q_i \cdot t_i</math>
Dabei ist <math>q_i</math> der Quotient (und <math>r_{i+1}</math> der Rest) der [[Division mit Rest|Division]] <math>r_{i-1} : r_i</math>.

Die Berechnung endet, sobald <math>r_{i+1} = 0</math> auftritt. Dann ist <math>r_i</math> der ggT, und es gilt <math>r_i = a\cdot s_i + b \cdot t_i</math>.

Ein Beispiel dazu, aber in kompakter Form, findet man auf der Seite Division mit Rest im [[Division mit Rest#Euklidischer Algorithmus|Abschnitt Euklidischer Algorithmus]].

== Beispiel für die rekursive Variante ==

Zu der Vorgabe der Zahlen 99 und 78 produziert der einfache euklidische Algorithmus die Folge von Divisionen mit Rest:

:<math>\begin{matrix}
\underline{99}&=&1\cdot \underline{78}+\underline{21}\\
\underline{78}&=&3\cdot \underline{21}+\underline{15}\\
\underline{21}&=&1\cdot \underline{15}+\underline{\ 6}\\
\underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}\\
\underline{6}&=&2\cdot \underline{\ 3}+\underline{\ 0}
\end{matrix}</math>

3 ist ein Teiler von 6 und damit der gesuchte größte gemeinsame Teiler von 99 und 78. Nun kann man diese Gleichungen rückwärts lesen und den Rest jeweils als Differenz der beiden anderen Terme darstellen. Setzt man diese Restdarstellungen rekursiv ineinander ein, so ergeben sich verschiedene Darstellungen des letzten Restes 3:

:<math>\begin{array}{rclcl}
\underline{\ 3}&=&\underline{15}-2\cdot \underline{\ 6}\\
&=&\underline{15}-2\cdot (\underline{21}-1\cdot \underline{15})&=&3\cdot\underline{15}-2\cdot \underline{21}\\
&=&3\cdot(\underline{78}-3\cdot \underline{21})-2\cdot \underline{21}&=&3\cdot\underline{78}-11\cdot \underline{21}\\
&=&3\cdot\underline{78}-11\cdot (\underline{99}-1\cdot \underline{78})&=&14\cdot \underline{78}-11\cdot \underline{99}
\end{array}</math>

Der größte gemeinsame Teiler ist so als ganzzahlige [[Linearkombination]] der beiden Ausgangszahlen 78 und 99 dargestellt.

In der eben dargestellten Berechnungsvorschrift muss man erst den letzten Schritt des einfachen euklidischen Algorithmus abwarten, bevor die Berechnung der gesuchten Koeffizienten beginnen kann. Man kann aber auch ebenso alle anderen Reste als ganzzahlige Linearkombination von 78 und 99 darstellen und die zugehörigen Koeffizienten in jedem Schritt des einfachen euklidischen Algorithmus mit bestimmen:

:<math>\begin{array}{rclcrclcl}
\underline{99}&=&1\cdot \underline{78}+\underline{21}&\iff&
\underline{21}&=&&&1\cdot\underline{99}-1\cdot \underline{78}\\
\underline{78}&=&3\cdot \underline{21}+\underline{15}&\iff&
\underline{15}&=&1\cdot\underline{78}-3\cdot \underline{21}&=&-3\cdot\underline{99}+4\cdot \underline{78}\\
\underline{21}&=&1\cdot \underline{15}+\underline{\ 6}&\iff&
\underline{\ 6}&=&1\cdot\underline{21}-1\cdot\underline{15}&=&4\cdot\underline{99}-5\cdot \underline{78}\\
\underline{15}&=&2\cdot \underline{\ 6}+\underline{\ 3}&\iff&
\underline{\ 3}&=&1\cdot\underline{15}-2\cdot \underline{\ 6}&=&-11\cdot\underline{99}+14\cdot \underline{78}
\end{array}</math>

== Tabellarische Darstellung ==
=== Rekursive Variante ===
Die Zwischenergebnisse beider Berechnungsmöglichkeiten lassen sich übersichtlich in Tabellen darstellen. Für die erste Variante, bei der die Folge der Divisionen mit Rest rückwärts aufgearbeitet wird, kann dies die folgende Gestalt annehmen:

{|
|
{| class="wikitable"
|-
! a
! b
! q
! s
! t
|-
| 99 || 78 || 1 || ||
|-
| 78 || 21 || 3 || ||
|-
| 21 || 15 || 1 || ||
|-
| 15 || 6 || 2 || ||
|-
| 6 || 3 || 2 || ||
|-
| 3 || 0 || || ||
|}
|
|
{| class="wikitable"
|-
! a
! b
! q
! s
! t
|-
| 99 || 78 || 1 || ||
|-
| 78 || 21 || 3 || ||
|-
| 21 || 15 || 1 || ||
|-
| 15 || 6 || 2 || ||
|-
| 6 || 3 || 2 || ||
|-
| 3 || 0 || || 1 || 0
|}
|
|
{| class="wikitable"
|-
! a
! b
! q
! s
! t
|-
| 99 || 78 || 1 || −11 || 14
|-
| 78 || 21 || 3 || 3 || −11
|-
| 21 || 15 || 1 || −2 || 3
|-
| 15 || 6 || 2 || 1 || −2
|-
| 6 || 3 || 2 || 0 || 1
|-
| 3 || 0 || || 1 || 0
|}
|
|}

Dabei wird zuerst, wie in der linken Tabelle, der einfache euklidische Algorithmus ausgeführt. Die [[Division mit Rest]] hat dabei immer die Form <math>a=q\cdot b+r</math> (anders gesagt, bei <math>q</math> handelt es sich um das Ergebnis der Ganzzahldivision von <math>a</math> durch <math>b</math>, mit Rest <math>r</math>), wobei <math>q</math> und <math>r</math> bestimmt werden. <math>q</math> wird in der Zeile vermerkt, das Paar <math>(b,r)</math> wird an die Stelle des Paars <math>(a,b)</math> in der nächsten Zeile eingetragen. Dieser Schritt wird solange wiederholt, bis in der Spalte von <math>b</math> eine Null steht.

Bis zu diesem Punkt wurde der einfache euklidische Algorithmus ausgeführt, und in der linken unteren Ecke (Spalte <math>a</math>) kann der größte gemeinsame Teiler abgelesen werden. In unserem Fall die Drei. Nun beginnt die Berechnung der ganzzahligen Koeffizienten <math>s</math> und <math>t</math>. In jeder Zeile soll dabei <math>3=s\cdot a+t\cdot b</math> gelten. Dementsprechend wird in der letzten Zeile <math>s=1</math> eingetragen, denn <math>3\cdot 1=3</math>. Da in der letzten Zeile der Spalte <math>b=0</math> steht, kann für <math>t</math> ein beliebiger Wert genommen werden, denn <math>0\cdot t=0</math>. Hier im Beispiel ist <math>t=0</math> gesetzt, es ergibt sich die mittlere Tabelle.

Nun arbeitet man sich von unten nach oben. Für das <math>s</math> nimmt man das <math>t</math> der darunterliegenden Zeile. Das <math>t</math> berechnet sich aus dem <math>q</math> der jeweiligen Zeile und dem <math>s</math> und <math>t</math> der darunterliegenden Zeile.
: <math>s = t_{\mathsf{alt}}</math>
bzw.
: <math>t = s_{\mathsf{alt}} - q \cdot t_{\mathsf{alt}}</math>

Für die vorletzte Zeile ergibt sich so <math>s = 0</math> und <math>t = 1 - 2 \cdot 0 = 1</math>, darüber dann <math>s = 1</math> und <math>t = 0 - 2 \cdot 1 = -2</math> usw.

Diesen Schritt wiederholen wir solange, bis die Tabelle ausgefüllt ist. Es ergibt sich die rechte Tabelle. Die Einträge für <math>s</math> und <math>t</math> in der ersten Zeile sind die gesuchten Werte. Der größte gemeinsame Teiler findet sich, wie schon erwähnt, in der unteren linken Ecke. Für das Beispiel gilt damit

: <math>3 = -11 \cdot 99 + 14 \cdot 78</math>

=== Iterative Variante ===
Gegeben sind wieder die Werte 99 und 78:

Wie sich aus dem Beispiel ablesen lässt, hängt der aktuelle Rechenschritt von den Zwischenergebnissen der zwei vorhergehenden Rechenschritte ab. Dem kann Rechnung getragen werden, indem bei der Initialisierung eine Hilfszeile vorangestellt wird. Weiter werden, der Übersicht halber, Hilfsvariablen <math>u</math> und <math>v</math> mit einer eigenen Spalte eingefügt.

{|
|
{| class="wikitable"
|- class="hintergrundfarbe6"
! a
! b
! q
! u
! s
! v
! t
|-
| 0 || 99 || 0 || 0 || 1 || 1 || 0
|-
| 99 || 78 || 1 || 1 || 0 || 0 || 1
|-
| 78 || 21 || 3 || 0 || 1 || 1 || −1
|-
| 21 || 15 || 1 || 1 || −3 || −1 || 4
|-
| 15 || 6 || 2 || −3 || 4 || 4 || −5
|-
| 6 || 3 || 2 || 4 ||−11 || −5 || 14
|-
| 3 || 0 || ||−11 || 26 || 14 ||−33
|}
|
|}

Um die jeweils nächste Zeile zu bestimmen, werden folgende Operationen ausgeführt:

* Es wird die Division mit Rest ausgeführt, <math>a=q\cdot b+r</math> und <math>a_{\rm neu}=b</math> sowie <math>b_{\rm neu}=r</math> gesetzt.
* Die neuen Werte der Hilfsvariablen werden aus der aktuellen Zeile übernommen, <math>u_{\rm neu}=s</math> und <math>v_{\rm neu}=t</math>.
* Die neuen Koeffizienten ergeben sich durch <math>s_{\rm neu}=u-q\cdot s</math> und <math>t_{\rm neu}=v-q\cdot t</math>

Durch diese Vorschrift gelten in jeder außer der ersten Zeile die Beziehungen

:<math>a=u\cdot a_{\rm orig}+v\cdot b_{\rm orig}</math> und <math>b=s\cdot a_{\rm orig}+t\cdot b_{\rm orig}</math>,

hier mit den Ausgangswerten <math>a_{\rm orig}=99</math> und <math>b_{\rm orig}=78</math>. Aus den letzten zwei Zeilen liest man daher ab, dass ''3'' der größte gemeinsame Teiler ist und <math>3=-11\cdot 99+14\cdot 78</math> gilt.

Ist man mit dieser Methode vertraut genug, so kann man in der Tabelle die Spalten <math>a,u</math> und <math>v</math> weglassen, da diese nur bereits weiter oben stehende Einträge wiederholen. Weitere Beispiele in dieser verknappten Form sind in den folgenden Tabellen dargestellt:

{|
|
{| class="wikitable"
|- class="hintergrundfarbe6"
! k.
! b
! q
! s
! t
|-
| −1. || aorig='''122''' || –|| 1 || 0
|-
| 0. || borig='''22''' || 5|| 0 || 1
|-
| 1. || 12 || 1|| 1 || −5
|-
| 2. || 10 || 1|| −1 || 6
|-
| 3. || '''2'''=ggT || 5|| '''2'''=s || '''-11'''=t
|-
| 4. || <s>0</s> || –|| – || –
|}
|
{| class="wikitable"
|- class="hintergrundfarbe6"
! k.
! b
! q
! s
! t
|-
| −1. || aorig='''120''' || –|| 1 || 0
|-
| 0. || borig='''23''' || 5 || 0 || 1
|-
| 1. || 5 || 4|| 1 || −5
|-
| 2. || 3 || 1|| −4 || 21
|-
| 3. || 2 || 1|| 5 || −26
|-
| 4. || '''1'''=ggT || 2|| '''-9'''=s || '''47'''=t
|}
|}

== Allgemeine mathematische Grundlage ==

Der euklidische Algorithmus erzeugt zu vorgegebenen ganzen Zahlen ''a'' und ''b'' (allgemein: Elementen eines euklidischen Rings) zwei Folgen: eine Folge <math>(q_k)_k</math> von Quotienten und eine Folge <math>(r_k)_k</math> von Resten, wobei <math>r_0=a,\;r_1=b</math>. In jedem Schritt <math>k=1,2,\ldots</math> gilt dabei

: <math>r_{k-1}=q_k\cdot r_k+r_{k+1}</math>, <math>|r_{k+1}|<|r_{k}|</math>.

Nach endlich vielen Schritten ergibt sich der Rest Null.

Wir gehen nun zu [[Restklasse]]n modulo ''b'' über. Es ist trivial zu sehen, dass <math>r_0=a=1\cdot a</math> und <math>r_1=b=0\cdot a+1\cdot b</math> Vielfache von <math>a</math> nach Hinzufügen oder Abziehen von Vielfachen von <math>b</math> sind. Genauer sind die Restklassen <math>[r_k]_b</math> Vielfache der Restklasse <math>[a]_b</math> für <math>k=0,1</math>, und nach Rekursionsvorschrift auch für <math>k=2,3,\ldots</math>. Es kann also eine Folge von Multiplikatoren <math>(s_k)_k</math> konstruiert werden, die mit <math>s_0=1</math> und <math>s_1=0</math> initialisiert ist, so dass

: <math>r_k\equiv s_k\cdot a\pmod b</math>

gilt. Es ergibt sich die rekursive Beziehung

: <math>s_{k-1}\equiv q_k\cdot s_{k}+s_{k+1}</math>.

Man kann diese Rekursion in folgende Abfolge von Schritten für den erweiterten euklidischen Algorithmus fassen:

* Erhalte <math>a</math> und <math>b</math> als Eingabe.
* Setze <math>k=0</math>, <math>r_0=a,\;r_1=b</math>, <math>s_0=1</math> und <math>s_1=0</math>.
* Wiederhole:
** Erhöhe <math>k</math> um eins.
** Bestimme den ganzzahligen Quotienten <math>q_k=r_{k-1}\;\div\;r_{k}</math>.
** Setze <math>r_{k+1}=r_{k-1}-q_k\cdot r_k</math> und <math>s_{k+1}=s_{k-1}-q_k\cdot s_k</math>.
* bis <math>r_{k+1}=0</math> gilt.
* Gib den Rest <math>r_k=\operatorname{ggT}(a,b)</math> und die Zahl <math>s_k</math> mit <math>\operatorname{ggT}(a,b)\equiv s_k\cdot a\pmod{b}</math> zurück.

Jeder Schritt enthält implizit auch einen Multiplikator <math>t_k=(r_k-s_k\cdot a) \div b</math>, wobei diese Division keinen Rest lässt. Die Folge <math>(t_k)_k</math> kann auch explizit bestimmt werden, es gelten <math>t_0=0</math>, <math>t_1=1</math> und

:<math>t_{k-1}\equiv q_k\cdot t_{k}+t_{k+1}</math>.

Nach dem letzten Schritt ergibt sich nun <math>\operatorname{ggT}(a,b)=s_k\cdot a+t_k\cdot b</math>

Der Übersicht halber werden beim händischen Rechnen auch noch die Hilfsfolgen <math>(a_k=r_{k-1})_k</math> und <math>(b_k=r_k)_k</math> sowie <math>(u_k=s_{k-1})_k</math> sowie <math>(v_k=t_{k-1})_k</math> mitgeführt.

== Algorithmus ==
=== Rekursive Variante ===

Für den erweiterten euklidischen Algorithmus existiert auch eine [[Rekursion|rekursive]] Variante, die durch den folgenden [[Pseudocode]] gegeben ist:<ref name="INTROALG">{{BibISBN|0262032937}}</ref>

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') <math>\leftarrow</math> ''extended_euclid''(b, a '''mod''' b)
4 (d,s,t) <math>\leftarrow</math> (d',t',s' – (a '''div''' b)t')
5 '''return''' (d,s,t)

Gleichbedeutend ist folgende mathematische Funktionsdefinition mit Fallunterscheidung:

: <math>\operatorname{extended\_euclid}(a,b)=
\begin{cases}
(a,1,0)&\text{wenn } b=0\\
(d',t',s'-t' (a \text{ div } b))&\text{mit }(d',s',t')=\operatorname{extended\_euclid}(b,a\ \text{mod}\ b)
\end{cases}</math>

=== Programmierung ===
Das folgende [[Programmiersprache|Programm]] in der [[Programmiersprache]] [[C++]] zeigt die Implementierung der [[Rekursive Programmierung|rekursiven]] Variante und der [[Iterative Programmierung|iterativen]] Variante. Die zwei Varianten werden jeweils in einer [[Funktion (Programmierung)|Funktion]] mit den [[Parameter (Informatik)|Parametern]] ''a'' und ''b'' sowie ''s'' und ''t'' implementiert. Die Parameter ''s'' und ''t'' sind [[Zeiger (Informatik)|Zeiger]] auf die berechneten Zahlen. Bei der Ausführung des Programms wird die Hauptfunktion ''main'' verwendet, die die Eingabe der beiden Zahlen über die Konsole ermöglicht und dann das Ergebnis der beiden Varianten dort ausgibt.<syntaxhighlight lang="c++">
#include <iostream>
using namespace std;

int gcdExtendedRecursive(int a, int b, int* s, int* t)
{
if (b == 0)
{
*s = 1;
*t = 0;
return a;
}
int s1, t1; // Deklaration der Variablen, die die Ergebnisse des rekursiven Aufrufs speichern
int d = gcdExtendedRecursive(b, a % b, &s1, &t1); // Rekursiver Aufruf der Methode
*s = t1;
*t = s1 - (a / b) * t1;
return d;
}

int gcdExtendedIterative(int a, int b, int* s, int* t)
{
*s = 1; // Initialisierung der Zeiger
*t = 0;
int u = 0; // Deklaration der lokalen Variablen
int v = 1;
while (b != 0)
{
int q = a / b;
int b1 = b; // Variable zum Zwischenspeichern
b = a - q * b;
a = b1;
int u1 = u; // Variable zum Zwischenspeichern
u = *s - q * u;
*s = u1;
int v1 = v; // Variable zum Zwischenspeichern
v = *t - q * v;
*t = v1;
}
return a;
}

// Hauptfunktion die das Programm ausführt
int main()
{
int a, b, s, t; // Deklaration der lokalen Variablen
cout << "Erste Zahl: "; // Ausgabe auf der Konsole
cin >> a; // Eingabe über die Konsole
cout << "Zweite Zahl: "; // Ausgabe auf der Konsole
cin >> b; // Eingabe über die Konsole
int d = gcdExtendedRecursive(a, b, &s, &t); // Aufruf der rekursiven Funktion
cout << "Groesster gemeinsamer Teiler: " << s << " * " << a << " + " << t << " * " << b << " = " << d << endl; // Ausgabe auf der Konsole
d = gcdExtendedIterative(a, b, &s, &t); // Aufruf der iterativen Funktion
cout << "Groesster gemeinsamer Teiler: " << s << " * " << a << " + " << t << " * " <

== Hinweise zur effizienten Computerimplementierung ==
[[Datei:Extended-euclidean-algorithm-runtime de.svg|mini|Darstellung der Anzahl der Schleifendurchläufe für zwei Zahlen <math>m</math> und <math>n</math>, für die die einfache Implementierung des erweiterten euklidischen Algorithmus verwendet wurde.]]

=== Darstellung mittels Matrizen ===

Versieht man die Variablen des euklidischen Algorithmus mit Indizes für den Iterationsschritt, so wird im Schritt <math>k</math> die Division mit Rest <math>m_k=n_k\cdot q_k+r_k</math> ausgeführt. Im Übergang zum nächsten Schritt wird <math>\,m_{k+1}=n_k</math> und <math>\,n_{k+1}=r_k=m_k-q_k\cdot n_k</math> gesetzt. Bildet man aus <math>m</math> und <math>n</math> einen [[Spaltenvektor]], so hat der gesamte Schritt eine Darstellung mit [[Matrix (Mathematik)|Übergangsmatrix]],

: <math>
\begin{pmatrix}m_{k+1}\\n_{k+1}\end{pmatrix}
= \begin{pmatrix}0&1\\1&-q_k\end{pmatrix}
\cdot \begin{pmatrix}m_{k}\\n_{k}\end{pmatrix}
</math>.

Terminiert der Algorithmus nach <math>L</math> Schritten, so gilt <math>\,n_{L+1}=r_L=0</math> und daher <math>\,m_{L+1}=n_L=\operatorname{ggT}(a,b)</math>. Setzt man die Bildungsvorschriften der Spaltenvektoren ineinander ein, so ergibt sich die Verbindung zwischen dem ersten und dem letzten Spaltenvektor durch ein [[Matrizenprodukt]],

: <math>\begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}
= \begin{pmatrix}0&1\\1&-q_L\end{pmatrix}
\cdot\ldots\cdot
\begin{pmatrix}0&1\\1&-q_1\end{pmatrix}
\cdot \begin{pmatrix}a\\b\end{pmatrix}
</math>.

Durch Multiplikation mit dem Zeilenvektor <math>(1,0)</math> wird die erste Zeile auf beiden Seiten extrahiert, somit gilt

: <math>\operatorname{ggT}(a,b)
= \begin{pmatrix}1&0\end{pmatrix}
\cdot
\begin{pmatrix}0&1\\1&-q_{L}\end{pmatrix}
\cdot\ldots\cdot
\begin{pmatrix}0&1\\1&-q_1\end{pmatrix}
\cdot \begin{pmatrix}a\\b\end{pmatrix}
</math>.

Die verschiedenen Arten, das Matrixprodukt der letzten Identität auszurechnen, ergeben die verschiedenen Varianten des erweiterten euklidischen Algorithmus. In der klassischen Variante, in welcher die Divisionen mit Rest von der letzten beginnend ausgewertet werden, entspricht der Bildung der Matrixprodukte beginnend von links. Diese entspricht dem nachfolgenden rekursiven Algorithmus. Es wird <math>(s_1,t_1)=(1,0)</math> gesetzt und rekursiv

: <math>(s_{k+1},t_{k+1})=(s_k,t_k)\begin{pmatrix}0&1\\1&-q_{L+1-k}\end{pmatrix}</math> für <math>k=1,\ldots ,L</math>

bestimmt. Am Ende gilt <math>\,\operatorname{ggT}(a,b)=s_{L+1}a+t_{L+1}b</math>. Es müssen aber zuerst alle Quotienten bestimmt werden, bevor der erste Rekursionsschritt ausgeführt werden kann.

Beginnt man die Produktbildung von rechts, so wird der Quotient der Division mit Rest in dem Augenblick benutzt, in dem er bestimmt wurde und kann danach vergessen werden. Dies entspricht dem am Anfang angegebenen Algorithmus, in welchem am Anfang

: <math>
\begin{pmatrix}s_1&t_1\\u_1&v_1\end{pmatrix}=I_2=\begin{pmatrix}1&0\\0&1\end{pmatrix}
</math> festgesetzt und <math>
\begin{pmatrix}s_{k+1}&t_{k+1}\\u_{k+1}&v_{k+1}\end{pmatrix}
= \begin{pmatrix}0&1\\1&-q_k\end{pmatrix}
\cdot
\begin{pmatrix}s_{k}&t_{k}\\u_{k}&v_{k}\end{pmatrix}
</math> für <math>k=1,\ldots ,L</math>

iteriert wird. Insgesamt ergibt sich damit

: <math>
\begin{pmatrix}s_{L+1}&t_{L+1}\\u_{L+1}&v_{L+1}\end{pmatrix}
= \begin{pmatrix}0&1\\1&-q_L\end{pmatrix}
\cdot\ldots\cdot
\begin{pmatrix}0&1\\1&-q_1\end{pmatrix}
</math>.

Am Ende gilt <math>\,\operatorname{ggT}(a,b)=s_{L+1}a+t_{L+1}b</math>, wobei wegen der Beziehungen <math>\,s_{L+1}=u_L</math> und <math>\,t_{L+1}=v_L</math> der letzte Iterationsschritt auch weggelassen werden kann.

== Siehe auch ==

* [[Euklidischer Algorithmus]]
* [[Steinscher Algorithmus]]

== Weblinks ==
* Universität Ulm: "Elementare Zahlentheorie" [https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.zawa/lehre/11elzahl/Skript.pdf]
* [http://www.inf.fh-flensburg.de/lang/krypto/algo/euklid.htm Iterative Variante in Java (Quellcode)]
* [http://arndt-bruenner.de/mathe/scripts/erweitertereuklid.htm JavaScript-Rechner mit Berechnungsdetails und Zwischenschritten]
* [https://www.netzwolf.info/mathematik/erweiterter-euklidischer-algorithmus.html Alternative Darstellung der Berechnung]
* {{TIBAV |19885 |Linktext=Erweiterter Euklidischer Algorithmus Teil 1 |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19885}}
* {{TIBAV |19886 |Linktext=Erweiterter Euklidischer Algorithmus Teil 2 |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19886}}
* {{TIBAV |19887 |Linktext=Erweiterter Euklidischer Algorithmus Teil 3 |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19887}}
* Hochschule Flensburg: [https://www.inf.hs-flensburg.de/lang/krypto/algo/euklid.htm Euklidischer Algorithmus]
* GeeksforGeeks: [https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/ Euclidean algorithms (Basic and Extended)]

== Einzelnachweise ==
<references />

[[Kategorie:Zahlentheoretischer Algorithmus]]

Erweiterter euklidischer Algorithmus - Versionsgeschichte

imported>Rigormath: /* Funktionsweise der iterativen Variante */ Link zu Divison mit Rest.