Aufgabe:
Bestimme ggT(42, 273) und löse anschließend die lineare diophantische Gleichung 42x + 273y = ggT(42, 273)
Problem/Ansatz:
Wir müssen das mit dem erweiterten Euklidischen Algorithmus lösen. Aber wenn ich die Schritte durchführe, kommt es zu einer quasi Endlosschleife:
a = [\( \frac{a}{b} \)] . b + a mod b
42 = 0 . 273 + 42
273 = 6 . 42 + 21
42 = 2 . 21 + 0
So weit so gut. Aber, wenn ich dann den erweiterten euklidischen Algoritmus anwende, passiert folgendes:
21 = 273 - 6 . 42
42 = 42 - 0 . 273
21 = 273 - 6 . 42 = 273 - 6 . (42 - 0 . 273) = (-6) . 42 + 273
Wenn ich 42 weiter ersetze, passiert immer dasselbe. Wäre die richtige Lösung dann
(-6) . 42 + 273 = 21 (btw. x = -6, y = 1) oder habe ich einen Fehler in meinem Ansatz? Ich will die Logik hinter dem euklidischen Algorithmus verstehen. Vielen Dank im voraus!