a^-1 modulo m Wie berechnen?

E

elite-noob

0
Hallo zusammen, ich habe das Problem das ich bei einer Berechnung eine Rechenoperation lösen muss die mir (weil nur Qualischüler) nicht ganz schlüssig ist

Würde ich z.B.

a^3 modulo m rechne wäre das ja klar
also 2^3 mod 4 = 8 mod 4 = 0

aber bei

5^-1 mod 48 verstehe ich aber nicht wie ich lösen soll, von der Seite wo ich komme ist das ein Teilproblem und wird so gerechnet

b=5^-1 mod 48 = 29

nun verstehe ich nicht sorecht wie die auf die 29 kommen...

Irgend ein Mathegenie hier der mir helfen könnte?

gruß
chris
 
Hallo,
5^(-1) mod 48 heißt einfach nur, es wird ein b gesucht, mit 5*b mod 48 = 1

Solch ein b lässt sich relativ leicht bestimmen, sofern es existiert. Dies geht mit dem erweiterten euklidischen Algorithmus, und zwar berechnet man die linear Kombination von 5 und 48 und hat dann solch eine Form:
5*b+48*c = 1

Und das b ist dann dein gesuchtes 5^(-1).

In diesem Fall wäre b=29, denn 5*29 mod 48 = 1
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben