Euklidischer Algorithmus
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
-
![{\displaystyle {}\operatorname {ggT} (r_{i+1},r_{i})=\operatorname {ggT} (r_{i},r_{i-1})\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3560af2aecfc173b18f8fc18958e7463ab06fac5)
- Es sei
der erste Index derart, dass
ist. Dann ist
-
![{\displaystyle {}\operatorname {ggT} (a,b)=r_{k-1}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a402d89377f646145432669e76fea36aaca2cde)