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?

---

9412 : 2880 = 3 R 772

Das bedeutet

9412 = 3 * 2880 + 772 oder eben
772 = 1 * 9412 - 3 * 2880

Ich stelle also den Rest mithilfe der Zahlen 9412 und 2880 dar.

Das hatte ich aber auch oben so nur als Einzeiler geschrieben.

Was dir helfen könnte, ist das einfach mit Excel oder sogar einem selbstgeschriebenen Computerprogramm nachzuvollziehen. Einem Computer musst du dabei ja genau mitteilen, wie du selber mit einem Algorithmus vorgehen würdest.

In Java hast du eigentlich alles, was du dafür benötigst.