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\ne 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 Elemente $r_0=a,r_1=b\ne 0$ eines euklidischen Bereiches $R$ mit euklidischer Funktion $\delta$ gegeben. Dann besitzt die Folge $r_i$,  $i=0,1,2,\dots$,  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\ge 2$  mit  $r_k=0$. 
3. Es ist

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

4. Es sei  $k\ge 2$  der erste Index derart, dass  $r_k=0$  ist. Dann ist

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

Beweis

1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
2. Solange  $r_i\ne 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

   $\mathrm{ggT}(a,b)=\mathrm{ggT}(b,r_2)=\mathrm{ggT}(r_2,r_3)=\dots =\mathrm{ggT}(r_{k-2},r_{k-1})=\mathrm{ggT}(r_{k-1},r_k)=\mathrm{ggT}(r_{k-1},0)=r_{k-1}.$

$◻$

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}]$ mithilfe 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 $ℂ$ 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.