Multiplikatives Inverses

Neue Frage »

Tenne Auf diesen Beitrag antworten »
Multiplikatives Inverses
Hallo zusammen,

ich soll 16^(-1) mod 13 berechnen. Laut Wolphramalpha und diversen anderen Tools soll dort 9 rauskommen.

Ich hab den Erweiterten Euklidischen Algorithmus wie folgt genutzt und komme auf das Ergebnis 4.
Was habe ich falsch gemacht?

13=0*16+13
16=1*13+3
13=4*3+1
3=3*1+0

Damit wäre bewiesen das der GGT(16,13) = 1 ist. Das bedeutet das 16 ein multiplikatives inverses hat.
Daher kann ich wie folgt weiter rechnen.

1=13-(4*3)
1=13-(4*(16-1*13))
1=1*13-4*16+4*13
1=5*13-4*16

Daraus folgt:
16^(-1)=4 mod 13.

Ich hoffe das ist einigermaßen nachvollziehbar?
Vielleicht kann mir jemand einen anderen Rechenweg vorschlagen, mit dem ich auf 9 als Ergebnis komme?
HAL 9000 Auf diesen Beitrag antworten »
RE: Multiplikatives inverses
Zitat:
Original von Tenne
1=5*13-4*16

Bis hierhin soweit richtig.

Zitat:
Original von Tenne
Daraus folgt:
16^(-1)=4 mod 13.

Nein: Daraus folgt .
Tenne Auf diesen Beitrag antworten »
RE: Multiplikatives inverses
Hallo HAL 9000 (geiler Film übrigens),

ich bin unabhängig von dir jetzt auch darauf gekommen das es -4 sein muss und nicht 4.

-4+13=9 und Somit habe ich mein Ergebnis.

Vielen Dank für die Bestätigung,

Tenne
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »