Inverse Modulo Rechner
Rechner zur Berechnung des multiplikativen Inversen mod x
Diese Funktion berechnet die multiplikative Inverse x aus einer ganzen Zahl a und modulo m.
Zur Berechnung geben Sie die natürlichen Zahlen a und m ein, dann klicken Sie auf den Button 'Rechnen'.
|
Beschreibung des multiplikativen Inversen
Das multiplikative Inverse einer Zahl \(a\) modulo \(m\) ist eine Zahl \(x\), sodass gilt: \[ a⋅x≡1(mod \ m)\] Die modulare multiplikative Inverse von einem Modulo \(m\) existiert nur, wenn \(a\) und \(m\) relativ Prim (ggt(a, m) = 1) sind.
Mit anderen Worten: \(x\) ist das multiplikative Inverse von \( a\) modulo \(m\), wenn das Produkt \( a⋅x \) bei Division durch \( m\) den Rest \( 1 \) lässt.
Berechnung des multiplikativen Inversen:
Es gibt mehrere Methoden, um das multiplikative Inverse zu berechnen. Die beiden gängigsten sind:
-
Erweiterter euklidischer Algorithmus
Der erweiterte euklidische Algorithmus findet nicht nur den größten gemeinsamen Teiler (ggT) von \(a\) und \(m\), sondern auch die Koeffizienten \(x\) und \(y\), sodass gilt \[a⋅x+m⋅y=ggT(a,m)\] Wenn \( ggT(a,m)=1\), dann ist \(x\) das multiplikative Inverse von \(a\) modulo \(m\).
-
Probieren (für kleine Zahlen)
Für kleine Zahlen kann man einfach alle möglichen Werte von \(x\) durchprobieren, bis man das passende Inverse findest.
Beispiel:
Finde das multiplikative Inverse von \(3\) modulo \(7\).
Schritt 1: Überprüfen, ob ein Inverses existiert
Berechne
\[ggT(3,7)=1\]
Da der ggT 1 ist, existiert ein multiplikatives Inverse.
Schritt 2: Berechnung mit dem erweiterten euklidischen Algorithmus
Finden von x und y, sodass:
\[ 3x+7y=1\]
Anwendung des erweiterten euklidischen Algorithmus:
\[7=2⋅3+1\] \[ 3=3⋅1+0\]
Rückwärtseinsetzen:
\[ 1=7−2⋅3\]
Daraus folgt:
\[ x=−2 \ \text{und} \ y=1\]
Da wir modulo 7 rechnen, nehmen wir \[x=−2 \ \text{mod} \ 7=5\].
Ergebnis:
Das multiplikative Inverse von 3 modulo 7 ist 5, denn:
\[ 3⋅5=15≡1(mod7)\]
Ein Video zu dem Thema finden Sie hier.
|
|