Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt/Beweis/Aufgabe/Lösung

Die Reste seien mit ${}r_{i}$ bezeichnet. 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. Daraus folgt 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}\,,$

dass der Algorithmus den größten gemeinsamen Teiler von ${}a$ und ${}b$

berechnet.

Zur gelösten Aufgabe