Frage von Albert30103, 64

Wie kann ich Inverse finden?

(a * b) mod n = 1. b ist Inverse von a. Wenn n Prim ist, ist diese Gleichung richtig: b = (a^(n - 2)) mod n. Kann diese Gleichung beweisen? Ich kann die Inverse mithilfe ggt finden. Danke im Voraus.

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von lks72, 47

Das folgt direkt aus dem kleinen Satz von Fermat. a^(n-1) • a = a^(n-1) =1 mod n nach Fermat.

Kommentar von Albert30103 ,

Danke

Kommentar von lks72 ,

Am Anfang muss es natürlich a^(n-2) heißen

Antwort
von kdreis, 6

a^(n-1) = 1 (kleiner Fermat). a^(n-2) = 1/a, also invers zu a.

Keine passende Antwort gefunden?

Fragen Sie die Community