Bestimmen Sie mit Hilfe des erweiterten Euklidischen Algorithmus ggT(a; b), sowie

Question

Seien a = 9412 und b = 2880. Bestimmen Sie mit Hilfe des erweiterten Euklidischen Algorithmus ggT(a; b), sowie
x; y in Z mit ggT(a; b) = x * a + y * b.

Die Lösung ist ggT(9412; 2880) = 4 und es gilt 4 = 97 * 9412 + 317 * 2880

Ich habe folgendes raus, was aber anscheinend falsch ist:

i         a       b         q    r     x      y

1     9412  2880        3   772   14    43

2     2880    772         3 564      4  -13

3       772     564         1 208     -1    4

4        564     208         2 148      3   -1

5        208       148         1 60       5    3

6        148         60         2   28      -2   5

7          60         28         2     4        1 -2

8          28          4          7     0         0  1

Answer 1

Bei mir sieht das so aus

Comments

Und wie bist du jetzt auf die x und y-Werte gekommen

---

Ich rechne dabei nur von oben nach unten und nicht von unten nach oben.

d.h.

772 = 1 * 9412 - 3 * 2880

564 = 1 * 2880 - 3 * 772
564 = 1 * 2880 - 3 * (1 * 9412 - 3 * 2880)
564 = -3 * 9412 + 10 * 2880

Das fand ich einfacher in Excel zu implementieren, weil ich ja nicht weiß wie lang die Tabelle wird.

---

Hier nochmal wie du es sicher haben wolltest

---

ahh okay da habe ich wohl einen Fehler in der Rechnung gemacht. Vielen Dank :)

---

Ich rechne dabei nur von oben nach unten und nicht von unten nach oben.

Wie kommst du auf 97 und -317 ohne von unten nach oben zu rechen, nutzt du nicht den erweiterteren Eukli. Algorithmus, oder hast du da einen anderen Trick, bei dem erweiterten komm ich immer durcheinander und verechne mich...

Oder hast du x und y ganz am Ende hinzugefügt?

---

In meiner zweiten Tabelle wird das x und y von unten nach oben gerechnet. Das ist das Schema, wie es auf Wikipedia steht.

In meiner ersten Tabelle rechne ich einfach von oben nach unten. Dort beginnt die Tabelle ja auch mit x = 1 und y = -3. Und daraus wird dann in der nächsten Zeile x = -3 und y = 10.

Sorry, wenn das Verwirrung gestiftet hat. Viele lernen das nach der Variante auf Wikipedia.

---

In meiner ersten Tabelle rechne ich einfach von oben nach unten. Dort beginnt die Tabelle ja auch mit x = 1 und y = -3. Und

Wie kommst du aber auf x =1 und y=-3 von oben nach unten rechnend?