+1 Daumen
431 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

aba div ba mod bdxy
99781213-1114
782131533-11
2115163-23
1562331-2
6320301

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 287 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 einfach und kostenlos

x
Made by a lovely community