Hilfe beim Beweis der Existenz des ggT

Question

Aufgabe:

Beweis der Existenz des ggT

Problem/Ansatz:

In meinen Unterlagen habe ich den Beweis zur Aussage: "In einem euklidischen RIng besitzen je zwei Elemenete a, b einen ggT" gefunden.

Zunächst wird eine Fallunterscheidung gemacht:

1. Ist b=0, so ist ggT(a, b)  = a

2. ist b ungleich 0 und ß die Betrangsfunktion im euklidischen Ring, so soll mit vollständiger Induktion über ß(b) ∈ N₀ gezeigt werden dass ein ggT existiert

Induktionsanfang: ß(b) = 0    Dann folgt dass der Rest auch 0 sein muss und somit b der ggT von a und b ist.

Induktionsschritt: Im Fall, dass der Rest r=0 ist folgt ggT(a,b)=b

Soweit so gut, weiter steht im Beweis: Im Fall r ≠ 0 folgt wegen ß(r) < ß(b) aus der Induktionsannahme, angewendet auf b und r, die Existenz von d = ggT(b, r)

Kann mir jemand diesen Satz etwas genauer erläutern? Wodurch genau wird im Induktionsschritt klar, dass d = ggT(b,r) existieren muss?

Danke im Voraus!

Answer 1

mit vollständiger Induktion über ß(b) ∈ N₀

Induktionsannahme:

Für alle \(x,y\) aus dem Ring mit \(\beta(y) < \beta(b)\) existiert \(\operatorname{ggT}(x,y)\)

Wodurch genau wird im Induktionsschritt klar, dass d = ggT(b,r) existieren muss?

Laut Induktionsannahme existiert \(\operatorname{ggT}(x,y)\) insbesondere für \(x=b, y=r\), weil \(\beta(y) = \beta(r) < \beta(b)\) ist.