Bestimme ggT(42, 273) und löse anschließend die lineare diophantische Gleichung 42x + 273y = ggT(42, 273)

Question

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!

Answer 1

Ich verstehe dich nicht. Mit

21 = 273 - 6 . 42

hast du bereits den ggT durch Linearkombination von 273 und 42 ausgedrückt und bist fertig.

In bekannter Tabellenform sieht das wie folgt aus

Comments

Uns wurde das so erklärt, dass wenn man den ggT mit dem euklidischen Algorithmus findet, dann kann man eine mögliche ganzzählige Lösung für die diophantische Gleichung mit dem erweiterten Euklid finden. Und wir ersetzen die Ergebnisse der Zwischenschritte im Algorithmus "bottom up". Daher kommen im zweiten Teil (wo man x und y der Gleichung finden muss)

42 = 0 . 273 + 42 wird zum 42 = 42 - 0 . 273

und

273 = 6 . 42 + 21 wird zu 21 = 273 - 6 . 42 

ind dann muss man die Zahlem ersetzen, um zu x und y zu kommen.