Euklidischer Algorithmus (Bereiche)/ggT/Invarianz/Fakt

Euklidischer Algorithmus

Es seien 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}\,.$

Zum Beweis, Alternativen Beweis erstellen