Wie komme ich von der Tabelle auf die 20?

Question

Aufgabe:

Führen Sie die folgenden Rechnungen in der angegebenen multiplikativen Grup-
pe durch. Nutzen Sie bei der Berechnung des multiplikativen Inversen eine Me-
thode Ihrer Wahl.
a) 9 : 16 in Z29×

Problem/Ansatz:

erweiterte euklid. Algorithmus angewendet        ri     si    ti
29            1    0
16            0    1
13   1       1    -1
3     1       -1    2
1     4       5    -9
0     3

Üblicherweise konnte ich an der Stelle von -9 diese als mutliplikative Inverse nutzen aber 20 ist die Inverse. 9 : 16 = 9 · 20 = 6 mod 29Wie komme ich von der Tabelle auf die 20?

Vielen Dank für eure Hilfe.

Answer 1

Die Zeile ist schon richtig. Rechne die mal nach: 5*29-9*16=145-144=1.

Was sagt dir das?

Noch ein Tipp: 20+9=29  ;-)

Comments

Vielen lieben Dank für die Antwort - erstmal.

5*29-9*16=145-144=1 ist die Probe von 1 = s * a / t * a

Und mir ist auch aufgefallen, dass die 29 - 9 = die Inverse 20 ergibt. Nur leider entzieht es sich gerade meinem Verständnis warum es so ist.

Hoffentlich, kannst du mir da gerade Licht ins dunkeln bringen. :)

Answer 2

Aus der Tabelle weißt du das -9 das Inverse von 16 modulo 29 ist.

Nun gilt aber

-9 Ξ -9 + 29 = 20 Modulo 29

Also ist auch 20 ein Inverses von 16 Modulo 29.