Euklidischer Algorithmus (Bereiche)/ggT/Invarianz/Fakt

Euklidischer Algorithmus

Es seien zwei Elemente eines euklidischen Bereiches mit euklidischer Funktion gegeben. Dann besitzt die Folge , , der euklidischen Reste folgende Eigenschaften.

  1. Es ist .
  2. Es gibt ein (minimales) mit .
  3. Es ist
  4. Es sei der erste Index derart, dass ist. Dann ist