0 Daumen
225 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Bei mir sieht die Tabelle wie folgt aus. Ich benutze allerdings dabei die Tabelle bei Wikipedia.

blob.png

Danach ist das Inverse von 29 30 Modulo 79.

29·30 - 11·79 = 1

Avatar von 477 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community