yuro123 |
Frage zum erweiterten euklid. Algorithmus
Ich habe mal eine kurze Frage zum erweiterten euklidischen Algorithmus. Und zwar hab ich mal im Anhang eine Tabelle hinterlegt die den ggT(a,n) = (28,75) ausrechnet und danach den erweiterten euklidischen Algorithmus nutzt um das inverse von 28 herauszubekommen.
Mir geht es hier darum, wie er das in der Tabelle auf der rechten Seite ausrechnet. Für das Beispiel im Anhang ist es verständlich.
Aber wie würde ich es für das Beispiel ggT(65, 238) durchführen?
so hab ich angefangen:
1 | n=238 | 4 | 57 | 10 | 1 | |
2 | | | | | 234 | 0 | 4 * 1
2 | 57 | 5 | 10 | 7 |
3 | | | | | ... | 1 | 5 * 234
3 | 10 | 1 | 7 | 3 |
4 | | | | |
4 | 7 | 2 | 3 | 1 |
5 | | | | |
5 | 3 | 3 | 1 | |
Bei 5*234 ist aber ein Fehler da es größer des mod 238 ist...
yuro123 hat dieses Bild (verkleinerte Version) angehängt:
|