Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt

Es seien ganze Zahlen $r_0=a$ und $r_1=b\ne 0$ gegeben.

Dann besitzt die Folge $r_i$, $i=0,1,2,\dots$ 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\ge 2$ mit $r_k=0$.
3. Es ist

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

   für alle  $i=1,\dots ,k$. 

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

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

Zum Beweis, Alternativen Beweis erstellen