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

Aus Wikiversity
Beweis
  1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
  2. Solange ist, wird die Folge der natürlichen Zahlen immer kleiner, so dass irgendwann der Fall eintreten muss.
  3. 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.

  4. Dies folgt aus (3) mit der Gleichungskette