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:
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von yuro123: 26.07.2015 15:02.
|