Euklidischer Algorithmus (Bereich)/ggT/Textabschnitt
Definition
Es seien Elemente (mit ) eines euklidischen Bereichs mit euklidischer Funktion 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 zwei Elemente eines euklidischen Bereiches mit euklidischer Funktion gegeben. Dann besitzt die Folge , , der euklidischen Reste folgende Eigenschaften.
- Es ist .
- Es gibt ein (minimales) mit .
- Es ist
- Es 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