Euklidischer Algorithmus (Bereiche)/ggT/Invarianz/Fakt/Beweis

Beweis

1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
2. Solange  $r_i\ne 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

   $\mathrm{ggT}(a,b)=\mathrm{ggT}(b,r_2)=\mathrm{ggT}(r_2,r_3)=\dots =\mathrm{ggT}(r_{k-2},r_{k-1})=\mathrm{ggT}(r_{k-1},r_k)=\mathrm{ggT}(r_{k-1},0)=r_{k-1}.$

Zur bewiesenen Aussage