Euklidischer Bereich/Euklidischer Algorithmus/Textabschnitt

Definition

Es seien Elemente $a, b$ (mit $b \neq 0$ ) eines euklidischen Bereichs $R$ mit euklidischer Funktion $δ$ 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.

Da die Division mit Rest in einem euklidischen Bereich nicht eindeutig sein muss, ist diese Folge im Allgemeinen nicht eindeutig bestimmt. Dies ist für den folgenden Algorithmus aber unerheblich (abgesehen davon, dass die eine oder andere Wahl der Reste den Algorithmus beschleunigen kann). Für $R = ℤ$ und $R = K [X]$ ist die Restfolge eindeutig bestimmt.

Satz

Es seien Elemente $r_{0} = a, r_{1} = b \neq 0$ eines euklidischen Bereiches $R$ mit euklidischer Funktion $δ$ gegeben. Dann besitzt die Folge $r_{i}$ , $i = 0, 1, 2, \dots$ , der euklidischen Reste folgende Eigenschaften.

Es ist $r_{i + 2} = 0 oder δ (r_{i + 2}) < δ (r_{i + 1})$ .
Es gibt ein (minimales) $k \geq 2$ mit $r_{k} = 0$ .
Es ist
$ggT (r_{i + 1}, r_{i}) = ggT (r_{i}, r_{i - 1}) .$
Es sei $k \geq 2$ der erste Index derart, dass $r_{k} = 0$ ist. Dann ist
$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 $δ (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
$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.
Dies folgt aus (3) mit der Gleichungskette
$ggT (a, b) = ggT (b, r_{2}) = ggT (r_{2}, r_{3}) = \dots = ggT (r_{k - 2}, r_{k - 1}) = ggT (r_{k - 1}, r_{k}) = ggT (r_{k - 1}, 0) = r_{k - 1} .$

◻

Mit dem euklidischen Algorithmus berechnet man also einen größten gemeinsamen Teiler. Indem man die im Algorithmus auftretenden Gleichungen von hinten nach vorne verwendet, erhält man auch eine Darstellung eines größten gemeinsamen Teilers als Linearkombination von $a$ und $b$ .