Euklydischer Algorithmus rückwärts, Fehler?

Question

Ich habe hierzu eine Frage/Problem.

Ich verstehe nicht, wie man den Euklydischen Algorithmus rechnet. Wie man den ggT bestimmt habe ich verstanden, aber das dann rückwärts anzuwenden verstehe ich nicht. Habe dann im Internet eine andere Form gefunden, wie man den euklydischen Algorithmus rückwärts lösen kann, was für mich einfacher aussah. Aber habe es mit der Aufgabe aus der Vorlesung probiert und irgendwo muss ich dort einen Fehler gemacht haben, da die Lösung beim roten Fragezeichen nicht aufgeht.

Answer 1

Eigentlich sieht das fast gut aus. Nur deine -16 sind verkehrt, dass sollten 26 sein. In meiner Tabelle habe ich statt s und t nur x und y genommen.

-7 * 189 + 26 * 51 = 3

Näheres zum Algorithmus

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

Comments

Achso ja klar, -3*-7=21

21+5=26.

Dann die Frage, warum das =3 ist, muss es nicht =21 sein?

---

Nein. Es geht darum den ggT als ganzzahlige Linearkombination der Ausgangszahlen darzustellen. Und der ggT war doch hier 3.

Auszug aus Wikipedia

Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler ggT(a, b) zweier natürlicher Zahlen a und b noch zwei ganze Zahlen s und t, die die folgende Gleichung erfüllen: ggT(a, b) = s * a + t * b

---

Ah okay, Damm verstehe ich das.

Aber habe das bei einer anderen Aufgabe probiert und komme auf das:

Da kommt für 28*1+12*(-3)≠4 raus ?

---

Auch dort hast du einen kleinen Fehler drin

1 * 28 + (-2) * 12 = 4

und damit auch

1 * 51 * 28 + (-2) * 51 * 12 = 4 * 51
51 * 28 + (-102) * 12 = 204

---

Habe das falsche q genommen, Fehler bemerkt.

Aber wie kommst du auf die 51?

---

4 * 51 sind doch 204

---

Also muss ich quasi das Ergebnis der Gleichung durch den ggT teilen und dass dann mal x und y multiplizieren, um auf die beiden Zahlen zu kommen?

---

Das wäre die einfachste Möglichkeit. Ich habe das oben auch nochmals nachgrtagen

1 * 28 + (-2) * 12 = 4

und damit auch

1 * 51 * 28 + (-2) * 51 * 12 = 4 * 51
51 * 28 + (-102) * 12 = 204

Aber ich dachte das verstest du, weil du das ja eigentlich schon hattest.

---

Habe das nur aus der Vorlesung abgeschrieben, aber nicht verstanden gehabt und wollte das jetzt halt nacharbeiten um zu verstehen. Da finde ich den Weg mit der Tabelle einfacher

---

Das mit der Tabelle ist einfacher zu notieren und auch einfacher zu rechnen. Für das Verständnis ist die Tabelle aber eher weniger hilfreich. daher wird die Tabelle im Unterricht auch erst kurz nach der formelmäßigen Herleitung gemacht. Es gibt recht gute Videos von Herrn Spannagel

https://www.youtube.com/results?search_query=erweiterter+euklidischer+algorithmus+spannagel

Einfach ansehen und nachvollziehen.