Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt

Es seien ganze Zahlen ${}r_{0}=a$ und ${}r_{1}=b\neq 0$ gegeben.

Dann besitzt die Folge ${}r_{i}$, ${}i=0,1,2,\ldots$, ${},$ der euklidischen Reste folgende Eigenschaften.

1. Es ist ${}r_{i+2}=0$ oder ${}r_{i+2}<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})\,$

   für alle ${}i=1,\ldots ,k$

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