Erweiterter euklidischer Algorithmus - was ist das "Abbruchkriterium"?

Erste Frage Aufrufe: 53     Aktiv: 04.06.2024 um 19:06

0
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
Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0
Wenn Du einmal Rest 1 hast, kannst Du den nächsten/letzten Schritt sparen, denn es ist ja klar, dass sich da Rest 0 ergibt. Und dann ist ggT=1. Aber es ist ja nicht jedesmal ggT=1, daher muss man dann bis zum Ende (Rest 0) rechnen.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 39.35K

 

Ok, ja vielen Dank. Mir ist bei einer weiteren Aufgabe "aufgefallen", dass der ggT natürlich nicht immer 1 ist.   ─   pemo24 04.06.2024 um 19:06

Kommentar schreiben