Ganze Zahlen mit erweitertem euklideschem Algorithmus finden

Question

Wir haben uns den euklidischen Algorithmus hier im Forum und in Büchern/Webseiten angeschaut aber kommen nicht auf eine Lösung bzw. auf einen logischen Rechenweg.

Die Aufgabe ist eigentlich einfach gestellt:

Finden Sie mit dem erweiterten euklidischen Algorithmus ganze Zahlen x und y mit 437x + 667y = gcd(437, 667)

Soweit komme ich:

$667 = 1 * 437 + 230$

$437 = 1 * 230 + 207$

$230 = 1 * 207 + 23$

$207 = 9 * 23 -> ggT$

II. Zurückrechnen

$23 = 230 - 1 * 207$

$= 230 - 1 * (437 -  1 * 230)$

$= ? *(430 - 1*230) - 1*230$

Der erste Teil funktioniert gut und einfach.

Bei der Zurückrechnung bin ich unsicher, wie ich das mache und kann bei den ganzen Lösungen, die ich mir angeschaut habe, kein Muster erkennen um die richtigen Faktoren zu finden.

Wenn mir dann noch jemand sagen kann wozu die Faktoren x und y im Endeffekt gut sind, wäre das ebenfalls klasse!

, Rich

Answer 1

Ich kenne zwar den euklidischen Algorithmus aber nicht den erweiterten euklidischen Algorithmus. Ich rechne das so: gcd(437, 667) = 23. Deshalb lässt sich die Gleichung durch 23 teilen. Das ergibt: 19x + 29y = 1. Für x = -1/10 und y = 1/10  ist diese Gleichung erfüllt.