+1 Daumen
110 Aufrufe

Aufgabe:

Ich befasse mich in meinem Informatikstudium derzeit mit dem Euklidischen Algorithmus. Dieser besagt dass a*x+b*y = ggT(a, b) ist. Wenn man sich jetzt den Euklidischen Algorithmus und die entstandene Tabelle mit den Spalten (a, b, a div b, a mod b, d, x, y) ansieht, dann ist festzustellen dass d bzw. der ggT(a, b) in jeder Zeile immer a mod b teilt, für a > b.

a, b, x, y:= Konstanten

a div b:= Ganzzahlige Division von a und b 

a mod b:= Rest von ganzzahliger Division von a und b

d:= ggT(a, b)

Beispieltabelle: ggT(99, 78) = d = 99x + 78y

a b a div b a mod b d x y
99 78 1 21 3 -11 14
78 21 3 15 3 3 -11
21 15 1 6 3 -2 3
15 6 2 3 3 1 -2
6 3 2 0 3 0 1

ggT(99, 78) = 3


Problem/Ansatz:

Ich würde gerne beweisen, warum dies der Fall ist.

Ich weiß dass ggT(a, b) = ax+by ist und dass dies (a mod b) teilen soll, also a*x+b*y | a mod b

Ich hätte jetzt gesagt, aus a mod b => r | (a-b).

Oben eingesetzt würde das dann heißen, aus a*x+b*y | a mod b => a*x+b*y | r | (a-b).

Jetzt ist die Frage wie ich am besten weiter vorgehen sollte, falls dies ein richtiger Lösungsansatz ist.

von

1 Antwort

+1 Daumen
 
Beste Antwort

Geht noch einfacher:

Wenn r = a mod b  ist, dann heißt das doch:

Es gibt ein x∈ℤ mit  a - b*x = r

und wenn d = ggT(a,b) ist, dann gilt

d | a    und d | b

==>  d | a    und d | b*x

und wenn es beides teilt, dann auch die Differenz;

denn   d | a    und d | b*x  heißt :

Es gibt   y,z  ∈ℤ   mit

d*y = a    und  d*z= b*x

==>   d*(y-x) = dy - dx =  a  -  b*x  . q.e.d.

von 185 k 🚀

vielen Dank für diese Antwort, habe mir das Ganze Problem nochmal angesehen mit diesen Überlegungen und hab es verstanden. Ich hab wohl einen Denkfehler gehabt, da ich dachte es wäre einfach über meinen Weg zu gehen :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community