Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt/Beweis

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 ${}r_{i}$ immer kleiner, sodass irgendwann der Fall ${}r_{i}=0$ eintreten muss.
3. Wenn ${}t$ ein gemeinsamer Teiler von ${}r_{i}$ und von ${}r_{i+1}$ ist, so zeigt die Beziehung

   ${}r_{i-1}=q_{i-1}r_{i}+r_{i+1}\,,$

   dass ${}t$ auch ein Teiler von ${}r_{i-1}$ 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}\,.$

Zur bewiesenen Aussage