Hallo Zusammen,

Ich versuche mir den erweiterten euklidischen Algorithmus klar zu machen. Was mir noch nicht klar ist, ob das "Abbruchkriterium" immer 0 sein muss.

Es soll 63 hoch -1 mod 431 mit Hilfe des euklidischen Algorithmus berechnet werden.

Ich habe folgende Gleichungen aufgestellt:

(1) 431 = 6 * 63 + 53
(2) 63 = 1 * 53 + 10
(3) 53 = 5 * 10 + 3
(4) 10 = 3 * 3 + 1
(5)  3 = 1 * 3 + 0

Damit ist das Auflösen zu Ende, da rechts eine 0 steht.

Wenn ich das Ganze z.B. mit 63 und 428 durchrechne sehen die Gleichungen so aus:

(1) 428 = 6 * 63 + 50
(2) 63 = 1 * 50 + 13
(3) 50 = 3 * 13 + 11
(4) 13 = 1 * 11  + 2
(5) 11 = 5 * 2 + 1
(6) 2 = 2 * 1 + 0

Meine Verständnisfrage, ist mit dem "Auflösen" immer dann Schluss, wenn rechts eine 0 steht? Oder kommt es auf die 1 an, da ja immer der ggT(a, b) berechnet werden soll? Dann wäre die letzte Gleichung jeweils überflüssig?

Danke und viele Grüße,
Peter