Wie berechne ich am schnellsten das Inverse in einem Restklassenring?

Question

einfaches Beispiel:

Geben Sie ein Element b Element aus {1,2,...71}  an, für das 13*b = 1 in Z*72 gilt.

Comments

Tipp: Das kann man z.B. mit dem erweiterten euklidischen Algorithmus lösen.

Answer 1

Die Frage "Wie berechne ich am schnellsten das Inverse in einem Restklassenring" kann ich auch nicht genau beantworten. Im vorliegenden Fall habe ich mir angeschaut, was der Mudul 72 so macht, nämlich: 72, 144, ... Dann habe ich mir angesehen, was die 13 hergibt: 13, 26,... 130, 143,... Also ist

13*b == 1 mod 72   |   * 11

−b ≡ 11 mod 72   |   * −1

b ≡ −11 mod 72   |   + 72

b ≡ 61 mod 72.

Probe:

13*61 = 793 = 720 + 72 + 1 ≡ 1 mod 72.

Comments

danke. ja habe jetzt die lösung endlich verstanden. :D und wieso das mit dem ggt zusammen hängt haha

Answer 2

Vielleicht liege ich richtig !

13 =0  *72    +13

72 = 5  * 13  +7

13 = 1  *7     +6

 7 =  1   *6    +1

 6 = 6  *1      + 0    → ggT ( 13 ; 72 ) =1

Comments

13*6 == 1 mod 72 ?

---

Alles klar! So ist es richtig .

---

ahh danke. ja ich weiss dass man das anhand des ggts berechnet...bzw. dass es damit zutun hat.

aber was ich nicht verstehe ist, 13*6 ist ja 78 ...modulo 72 ist doch 6.
tut mir leid.ich glaube ich habe einen denkfehler.

und wie kommt man auf die 6? :/