Euklidischer Algorithmus/Z/ggT/Invarianz/Fakt

Seien ganze Zahlen ${}r_{0}=a$ und ${}r_{1}=b\neq 0$ gegeben.

Dann besitzt die Folge ${}r_{i}$ , ${}i=0,1,2,\ldots$ , ${},$ der euklidischen Reste folgende Eigenschaften.

Es ist ${}r_{i+2}=0$ oder ${}r_{i+2}<r_{i+1}$ .

Es gibt ein (minimales) ${}k\geq 2$ mit ${}r_{k}=0$ .

Es ist
${}\operatorname {ggT} (r_{i-1},r_{i})=\operatorname {ggT} (r_{i},r_{i+1})\,$

für alle ${}i=1,\ldots ,k$

Sei ${}k\geq 2$ der erste Index derart, dass ${}r_{k}=0$ ist. Dann ist
${}\operatorname {ggT} (a,b)=r_{k-1}\,.$

Zum Beweis, Alternativen Beweis erstellen

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.