+1 Daumen
4,1k Aufrufe

einfaches Beispiel:


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

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

2 Antworten

+1 Daumen

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.

Avatar von

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

0 Daumen

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

Avatar von 2,3 k
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? :/

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community