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 :)