# Euklidischer Algorithmus/Z/Zi/Einführung/Textabschnitt

Euklidische Bereiche heißen so, weil in ihnen der euklidische Algorithmus ausgeführt werden kann.

## Definition

Es seien Elemente $a,b$ (mit $b\neq 0$) eines euklidischen Bereichs $R$ mit euklidischer Funktion $\delta$ gegeben. Dann nennt man die durch die Anfangsbedingungen $r_{0}=a$ und $r_{1}=b$ und die mittels der Division mit Rest
    $r_{i}=q_{i}r_{i+1}+r_{i+2}\,$
rekursiv bestimmte Folge $r_{i}$ die Folge der euklidischen Reste.

## Satz

Es seien zwei Elemente $r_{0}=a,r_{1}=b\neq 0$ eines euklidischen Bereiches $R$ mit euklidischer Funktion $\delta$ gegeben. Dann besitzt die Folge $r_{i}$, $i=0,1,2,\ldots$, der euklidischen Reste folgende Eigenschaften.
* Es ist $r_{i+2}=0{\text{ oder }}\delta (r_{i+2})<\delta (r_{i+1})$.
* Es gibt ein (minimales) $k\geq 2$ mit $r_{k}=0$.
* Es ist
    $\operatorname {ggT} (r_{i+1},r_{i})=\operatorname {ggT} (r_{i},r_{i-1})\,.$
* Es sei $k\geq 2$ der erste Index derart, dass $r_{k}=0$ ist. Dann ist
    $\operatorname {ggT} (a,b)=r_{k-1}\,.$

### Beweis

* Dies folgt unmittelbar aus der Definition der Division mit Rest.
* Solange $r_{i}\neq 0$ ist, wird die Folge der natürlichen Zahlen $\delta (r_{i})$ immer kleiner, sodass irgendwann der Fall $r_{i}=0$ eintreten muss.
* Wenn $t$ ein gemeinsamer Teiler von $r_{i+1}$ und von $r_{i+2}$ ist, so zeigt die Beziehung dass $t$ auch ein Teiler von $r_{i}$ und damit ein gemeinsamer Teiler von $r_{i+1}$ und von $r_{i}$ ist. Die Umkehrung folgt genauso.
    $r_{i}=q_{i}r_{i+1}+r_{i+2}\,,$
* Dies folgt aus (3) mit der Gleichungskette
    $\operatorname {ggT} (a,b)=\operatorname {ggT} (b,r_{2})=\operatorname {ggT} (r_{2},r_{3})=\ldots =\operatorname {ggT} (r_{k-2},r_{k-1})=\operatorname {ggT} (r_{k-1},r_{k})=\operatorname {ggT} (r_{k-1},0)=r_{k-1}\,.$
$\Box$
Als Beispiel zum Euklidischen Algorithmus lösen wir die folgende Aufgabe.
Aufgabe
Bestimme in $\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von $1071$ und $1029$.
Lösung
Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:
    $1071=1\cdot 1029+42\,,$
    $1029=24\cdot 42+21\,,$
    $42=2\cdot 21+0\,.$
Der größte gemeinsame Teiler von 1071 und 1029 ist somit 21.
Aufgabe
Bestimme in ${\mathbb {Z} }[{\mathrm {i} }]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von $7+4{\mathrm {i} }$ und $5+3{\mathrm {i} }$.
Lösung
Wir setzen $a=7+4{\mathrm {i} }$ und $b=5+3{\mathrm {i} }$ und führen die Division mit Rest $a/b$ durch. Es ist (in ${\mathbb {C} }$ oder in $\mathbb {Q} [{\mathrm {i} }]$)
    ${\frac {a}{b}}={\frac {7+4{\mathrm {i} }}{5+3{\mathrm {i} }}}={\frac {(7+4{\mathrm {i} })(5-3{\mathrm {i} })}{(5+3{\mathrm {i} })(5-3{\mathrm {i} })}}={\frac {47-{\mathrm {i} }}{34}}={\frac {47}{34}}-{\frac {1}{34}}{\mathrm {i} }\,.$
Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist $1$, sodass die Division mit Rest ergibt:
    $a=1\cdot b+r{\text{ mit }}r=a-b=2+{\mathrm {i} }.$
Die nächste durchzuführende Division ist somit
    ${\frac {b}{r}}={\frac {5+3{\mathrm {i} }}{2+{\mathrm {i} }}}={\frac {(5+3{\mathrm {i} })(2-{\mathrm {i} })}{(2+{\mathrm {i} })(2-{\mathrm {i} })}}={\frac {13+{\mathrm {i} }}{5}}={\frac {13}{5}}+{\frac {1}{5}}{\mathrm {i} }\,.$
Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist $3$, sodass die Division mit Rest ergibt:
    $b=3\cdot r+s{\text{ mit }}s=b-3r=5+3{\mathrm {i} }-3(2+{\mathrm {i} })=-1.$
Da dies eine Einheit ist, sind $a=7+4{\mathrm {i} }$ und $b=5+3{\mathrm {i} }$ teilerfremd.
* ↑ Da wir einen euklidischen Bereich ohne Eindeutigkeitsbedingung in der Division mit Rest definiert haben, ist diese Restfolge nicht unbedingt eindeutig bestimmt. Die relevanten Eigenschaften hängen aber nicht von Auswahlen ab und in allen wichtigen Beispielen ist die Division mit Rest eindeutig.