Euklidischer Algorithmus/Z/ggT/Textabschnitt

Aus Wikiversity



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.

  1. Es ist oder .
  2. Es gibt ein (minimales) mit .
  3. Es ist

    für alle

  4. Sei der erste Index derart, dass ist. Dann ist

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