Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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
Zum Beweis, Alternativen Beweis erstellen