Erweiterter euklidischer Algorithmus

[freakC++]

Hallo zusammen,

ich suche ein x und ein y, damit die Gleichung 132x + 72y = 1 erfüllt ist. Dazu möchte ich den erweiterten Euklidischen Algorithmus anwenden. Zunächst führe ich den ganz normalen Euklid durch und berechne dann mit diesen Formeln die Koeffizienten:

$x_{neu} = y_{alt}$
$y_{neu} = x_{alt} - q \cdot y_{alt}$

Dabei ist Q der ganzzahlige Quotient. Leider stimmt mein Ergebnis nicht. Meine Rechnung lautet:

132 : 72 = 1 Rest 60 x4 = -1; y4 = 2
72 : 60 = 1 Rest 12 x3 = 1; y3 = -1
60 : 12 = 5 Rest 0 x2 = 0; y2 = 1
12 : 0 x1 = 1; y1 = 0

Mein Ergebnis wäre also x = -1 und y = 2. Doch das stimmt nicht und ich finde einfach nicht den Fehler. Könnt ihr mir da weiterhelfen?

Vielen Dank
LG, freakC++

[freakC++]

Ohh...durch ein bisschen Nachlesen ist mir klar geworden, dass ich den Algorithmus falsch verstanden habe. Es kommt nich 1 heraus, sondern immer der ggT, der hier gerade 12 ist.

Daher stimmt mein Ergebnis, denn

132 * (-1) + 2 * 72 = 12.

Also, löscht meinetwegen diesen Thread oder schließt ihn, aber vielleicht macht ein anderer auch mal diesen doofen Fehler

Liebe Grüße
freakC++