euklidischer Alg. Beweis, dass rn gemeinsamer Teiler ist

Question

Aufgabe:

Euklidischer Algorthmus Beweis

Problem/Ansatz:

Wie kann man zeigen, dass unter Anwendung des euklidischen Algorithmus der letzte Rest r_n ungleich 0 ein gemeinsamer Teiler von a und b ist? Als Tipp soll man sich den Algorithmus von hinten nach vorne anschauen.

Um zu zeigen, dass r_n der "größte" gemeinsame Teiler ist, lautet meine Idee wiefolgt:

Sei d=ggt(a,b) und t Element aus R, für das gilt: t|a und t|b dann folgt, dass t|ggt(a,b). Da t den ggt von a und b teilt, muss folgendes gelten t <= ggt(a,b) und da t beliebig gewählt war, gilt dies für alle gemeinsamen Teiler von a und b, wodurch kein gemeinsamer Teiler ex., der größer als d ist. Macht das Sinn?

Danke im Voraus!

Answer 1

Hallo

in deinem Beweis kommt ja rn, also der letzte Rest gar nicht vor? was du sagst, : wenn d=ggT(a,b) ist ist es wirklich der größte Teiler, aber das sagt doch schon der Name?

Sieh dir wirklich den euklidischen Als. an warum erzeugt er mit rn den ggT

Gruß lul

Answer 2

Letzte Zeile:

a_n= k_n * b_n + 0

Damit ist b_n ein Teiler von a_n (und damit größter gemeinsamer Teiler von a_n und von b_n.

Zeile darüber:

a_(n-1)= k_(n-1) * b_(n-1) + r_(n-1).

Nun dürfen wir nicht vergessen, dass b_(n-1) das spätere a_n wird und r_(n-1) eine Zeile tiefer zu b_n wird.

Damit können wir die Zeile auch schreiben als

a_(n-1)= k_(n-1) * a_(n) + b_n

Da b_n ein Teiler von a_n war, ist b_n auch ein Teiler des Vielfachen k_(n-1) * a_(n), und b_n ist ein Teiler der Summanden b_n selbst.

b_n ist somit ein Teiler der Summe k_(n-1) * a_(n) + b_n, und diese Summe ist nichts weiter als der Term für a_(n-1).

Fazit: Weil b_n ein Teiler von a_n ist, ist b_n auch ein Teiler von a_(n-1).

Fortsetzung noch eine Zeile höher: Weil b_n ein Teiler von a_(n-1) ist, ist b_n auch ein Teiler von a_(n-2) usw.