0 Daumen
84 Aufrufe

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!

von

1 Antwort

0 Daumen

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

blob.png

von 439 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community