Euklidischer Algorithmus/Z/ggT/Textabschnitt
Definition
Es seien zwei ganze Zahlen (mit ) gegeben. Dann nennt man die durch die Anfangsbedingungen und und die mittels der Division mit Rest
rekursiv bestimmte Folge die Folge der euklidischen Reste.
Satz
Es seien ganze Zahlen und gegeben.
Dann besitzt die Folge , , der euklidischen Reste folgende Eigenschaften.
- Es ist oder .
- Es gibt ein (minimales) mit .
- Es ist
für alle
- Sei
der erste Index derart, dass
ist. Dann ist
Beweis
- Dies folgt unmittelbar aus der Definition der Division mit Rest.
- Solange ist, wird die Folge der natürlichen Zahlen immer kleiner, so dass 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