Wie berechnet man inverse Zahl? Beispiel

Question

Aufgabe:

Wie berechnet man die zu 10 mod 31 inverse Zahl?

mein Ansatz: 10*4 = 40 ≡ 9 mod31

                    9*4 = 32 ≡ 1 mod31

                   x= 4*4 ≡ ....

Comments

Hallo Lara,

9*4=36

:-)

---

Wie berechnet man die zu 10 mod 31 inverse Zahl

z.B. mit dem erweiterten euklidischen Algorithmus. da ggT(10,31) = 1

existieren ganze Zahlen u,v mit 10u+31v = 1

modulo 31 ist dann \( 10u \equiv 1 \mod (31) \)

Wie der Algorithmus funktioniert kannst du dir z.B. auf Wikipedia durchlesen oder auch auf YouTube anschauen.

Answer 1

10*4=40 → 9

9*4=36 → 5

5*7=35 → 4

4*8=32 → 1

4*4*7*8=28*32 → 28*1=28

:-)

Comments

Hey MontyPython,

danke dir für die schnelle Antwort.

Ich hab nur nh Frage wie man auf 28 kommt zb:

x = 4 * 4 * 7 * 8 = 28?

muss man da die zahl die bei 4 * 4 * 7 * 8 raus kommt durch 31 dividieren?

da kommt ja dann 896 : 31=28 (eig 28,9 aber das zu 28 abrunden?)

---

Du musst Ganzzahldivision durchführen.
896 ÷ 31 = 28 Rest 28
Der Rest ist dann die gesuchte Zahl.
Oder du erkennst, dass 32 den Rest 1 hat.
:-)

Answer 2

Hallo

10*3=-1 mod31

deshalb 10*3*10*3=1mod 31 also 10*90=1mod 31

und dann 90=28mod 31

also 10*28=1mod 30

lul