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


Die Reste seien mit bezeichnet. Wenn ein gemeinsamer Teiler von und von ist, so zeigt die Beziehung

dass auch ein Teiler von und damit ein gemeinsamer Teiler von und von ist. Die Umkehrung folgt genauso. Daraus folgt mit der Gleichungskette

dass der Algorithmus den größten gemeinsamen Teiler von und

berechnet.