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.
