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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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.
Zur gelösten Aufgabe