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.

1. Es ist ${}r_{i+2}=0{\text{ oder }}\delta (r_{i+2})<\delta (r_{i+1})$.
2. Es gibt ein (minimales) ${}k\geq 2$ mit ${}r_{k}=0$.
3. Es ist

   ${}\operatorname {ggT} (r_{i+1},r_{i})=\operatorname {ggT} (r_{i},r_{i-1})\,.$

4. Es sei ${}k\geq 2$ der erste Index derart, dass ${}r_{k}=0$ ist. Dann ist

   ${}\operatorname {ggT} (a,b)=r_{k-1}\,.$

Beweis

1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
2. 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.
3. Wenn ${}t$ ein gemeinsamer Teiler von ${}r_{i+1}$ und von ${}r_{i+2}$ ist, so zeigt die Beziehung

   ${}r_{i}=q_{i}r_{i+1}+r_{i+2}\,,$

   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.

4. 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.