Aufgabe:
Berechnen Sie die folgenden multiplikativen Inverse mit dem erweiterten euklidischen Algorithmus.
29^-1 in Z79
Problem/Ansatz:
Habe die euklidische Tabelle erstellt
ri si ti
79 1 0
29 0 1
21 2 1 -2
8 1 -1 2
5 2 3 -6
3 1 -4 8
2 1 7 -14
1 1 -11 22
0 2 - -
Jetzt hab ich nur ein Verständnisproblem. Bei einer Aufgabenstellung mit. 2 : 29 , wäre jetzt normalerweise an der Stelle von 22 die Inverse von 29. Das stimmt ja irgendwie nicht.
Meine Frage wäre jetzt, falls die Tabelle richtig ausgefüllt ist was genau wäre der nächste Schritt und oder überhaupt das Ziel dieser Aufgabe. Bisher habe ich jetzt gedacht, dass der Satz von Euler bei x^-1 in Zx dafür gedacht ist.
Vielen lieben Dank für die Hilfe.
