Multiplikatives Inverses im Modulo?

Wie macht man das?

z.B. das multiplikative Inverse von 3 in Z₇ finden.

Dann heißt das doch folgendes

3 * x^-1 = 1 mod 20

Wie kommt man denn auf das richtige x ?

Answer 1

[Rammstein53]

Falls mit Z₇ der Restklassenring modulo 7 gemeint ist, enthält der die Elemente {0,1,2,3,4,5,6}. Für die Inverse I von 3 muss gelten:

3*I modulo 7 = 1

Lösung I = 5, denn 3*5 = 15 und 15 modulo 7 = 1

Die Lösung wird durch probieren oder durch mehr oder weniger komplexe Algorithmen ermittelt. Eine einfache Formel zur Lösung gibt es nicht.