Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt/Beweis
Erscheinungsbild
Beweis
- Dies folgt unmittelbar aus der Definition der Division mit Rest.
- Solange ist, wird die Folge der natürlichen Zahlen immer kleiner, sodass irgendwann der Fall eintreten muss.
- 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.
- Dies folgt aus (3) mit der Gleichungskette