Euklidischer Bereich/Euklidischer Algorithmus/Textabschnitt

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$

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