Modulare Inverse Rechner

Willkommen beim Modulare-Inverse-Rechner! Er hilft dir immer dann, wenn du die modulare multiplikative Inversionen oder modulare additive Inversionen bestimmen musst.

Wenn du dir nicht sicher bist, was der modulare Kehrwert ist, scrolle nach unten! Wir geben dir alle notwendigen Definitionen und zeigen dir, wie du die modulare Inverse schriftlich findest!

Bevor wir lernen, was die modulare Inverse (modularer Kehrwert) ist, müssen wir uns mit der Kongruenzrelation vertraut machen.

Sei n eine natürliche Zahl (ungleich Null). Zwei ganze Zahlen a und b sind kongruent modulo n, wenn sie beide den gleichen Rest haben, wenn sie durch n geteilt werden. Genauso verhält es sich, wenn die Differenz a - b durch n mit Null als Rest teilbar ist, d. h. wenn a - b ein Vielfaches von n ist.

Wir bezeichnen die Tatsache, dass a und b modulo n kongruent sind, mit:

a ≡ b (mod n).

Schauen wir uns zwei Beispiele an.

• Beispiel 1:

  14 und 99 sind kongruent modulo 5:

  14 ≡ 99 (mod 5),

  denn 99 - 14 = 85 und 85 ist ein Vielfaches von 5. Das bedeutet, dass 14 und 99 den gleichen Rest haben, wenn sie durch 5 geteilt werden:

  14 mod 5 = 4

  99 mod 5 = 4

• Beispiel 2:

  14 und 99 sind nicht kongruent modulo 7.

  Das liegt daran, dass 99 - 14 = 85 und 85 kein Vielfaches von 7 ist. Es reicht also zu prüfen, ob 14 und 99 unterschiedliche Reste haben, wenn sie durch 7 dividiert werden:

  14 mod 7 = 0

  99 mod 7 = 1

Wenn du mehr über die Modulo-Operation und insbesondere über ihre praktischen Anwendungen erfahren möchtest, besuche unseren Modulo Rechner.

Wir sind nun bereit zu lernen, was die modulare Inverse (auch modularer Kehrwert genannt) ist!

Seien a und x ganze Zahlen. Wir sagen, dass x ein modulares Inverses von a ist, wenn eine algebraische Operation auf x und a das Identitätselement ergibt.

Je nachdem, ob es sich bei der Operation um eine Addition oder Multiplikation handelt, unterscheiden wir zwei Arten von modularen Inversen: additive und multiplikative.

Lass uns mehr über diese beiden Begriffe sprechen:

Modulare additive Inverse

Im Fall der Addition ist das Identitätselement 0. Wir sagen dann, dass x ein additiver Kehrwert von a modulo m ist, wenn a + x und 0 modulo m kongruent sind:

a + x ≡ 0 mod m

Ein additiver Kehrwert von a modulo m existiert immer für jedes a und m. Er ist durch eine beliebige Zahl der Form -a + k ∙ m gegeben, wobei k eine ganze Zahl ist. Normalerweise möchten wir den Kehrwert im Bereich {0, ... , m - 1}, d. h. in der Gruppe der Reste der Division durch m erhalten.

Wie berechne ich die modulare additive Inverse schriftlich? Hier sind die Schritte, die du befolgen kannst, um die modulare Kehrwertsumme von a modulo m zu finden:

1. Schreibe -a auf.
2. Schreibe die Zahlen auf, die durch wiederholtes Addieren oder Subtrahieren von m zu a entstehen.
3. Wähle die Zahl, die zwischen 0 und m - 1 liegt.

Lass uns sehen, wie das funktioniert!

• Beispiel 1:

  Wir möchten den additiven Kehrwert von 4 modulo 30 finden.

  Die Zahlen der Form 4 + 30k sind: ..., -4, 26, 56, ....

  In der Gruppe {0, ..., 29} ist der modulare Kehrwert von 4 modulo 30 also 26.

• Beispiel 2:

  Wir möchten den additiven Kehrwert von 44 modulo 13 finden.

  Die Zahlen der Form -44 + 13k sind: ..., -44, -31, -18, -5, 8, 22....

  In der Gruppe {0, ..., 12} ist der modulare Kehrwert von 44 modulo 13 also 8.

Modulare multiplikative Inverse

Erinnere dich daran, dass das Identitätselement der Multiplikation 1 ist. Daher ist x ein multiplikativer Kehrwert von a modulo m, wenn a ∙ x und 1 modulo m kongruent sind:

a ∙ x ≡ 1 mod m

Im Gegensatz zu additiven Inversen existiert die multiplikative modulare Inverse nicht immer! Wenn sie jedoch existiert, erfüllen alle Zahlen der Form x + k ∙ m die erforderliche Kongruenz. Insbesondere kannst du in solchen Fällen immer die Lösung (genau eine!) im Bereich {1, ... , m - 1} finden.

Ein Beispiel

Es gibt keinen multiplikativen modularen Kehrwert von 2 modulo 6. Du kannst diese Behauptung überprüfen, indem du feststellst, dass die Operation 2 ∙ x (mod 6) für x ∊ {1, 2, 3, 4, 5} nicht 1 ergibt.

Es ist wichtig, dass du dir merkst, dass der multiplikative modulare Kehrwert von a modulo m nur dann existiert, wenn a und m teilerfremd sind, d. h. ihr größter gemeinsamer Teiler (ggT) gleich eins ist. Wenn m eine Primzahl ist, dann existiert der modulare Kehrwert von m für jedes a ≠ 0, das kein Vielfaches von m ist.

Die ganze Theorie der modularen Inversion mag etwas abstrakt erscheinen und du fragst dich wahrscheinlich: „Warum sollte sich jemand für modulare multiplikative Inversionen interessieren?“ Nun, du solltest wissen, dass die Berechnung von modularen multiplikativen Inversen in der Kryptografie und insbesondere bei der RSA-Verschlüsselung unerlässlich ist. Das bedeutet, dass modulare multiplikative Inversionen deine Kreditkarte schützen!

Die schnellste Methode zur Bestimmung von multiplikativen modularen Inversen ist natürlich unser Modulare-Inverse-Rechner! 😉 Wenn du jedoch lernen möchtest, wie du den modularen Kehrwert von Hand ermitteln kannst, schau dir den nächsten Abschnitt an.

In diesem Abschnitt erklären wir, wie man die multiplikative modulare Inverse findet. Es gibt drei Hauptmethoden:

• Die einfache Methode (auch Brute-Force-Methode genannt, sie ist einfach, aber langsam);
• Den erweiterten euklidischen Algorithmus (schneller, funktioniert in allen Fällen); und
• Den kleinen Satz von Fermat (schneller, hübscher, funktioniert aber nur in einigen Fällen).

Egal, welche Methode du verwendest, der erste Schritt besteht darin, sicherzustellen, dass die multiplikative modulare Inverse existiert: Erinnere dich daran, dass du prüfen musst, ob a und m teilerfremd sind, d. h. ob ggT(a,m) = 1. Dafür kannst du unseren ggT und kgV Rechner 🇺🇸 verwenden.

Einfache Methode

Bei dieser Methode testest du alle Zahlen aus der Gruppe {0, ..., m - 1} aus. Für jede Zahl x aus dieser Gruppe berechnest du a ∙ x mod m, d. h. den Rest aus der Division von a ∙ x durch m.

Der modulare Kehrwert von a modulo m ist der Wert von x, für den dieser Rest gleich 1 ist.

Erweiterter euklidischer Algorithmus

Die zweite Methode verwendet die Identität von Bézout und den erweiterten euklidischen Algorithmus.

Bézout's Identität. Nehmen wir an, dass a und b ganze Zahlen sind. Es gibt zwei ganze Zahlen x und y, sodass: a ∙ x + b ∙ y = ggT(a, b).

Erinnere dich daran, dass der erweiterte euklidische Algorithmus uns erlaubt, ggT(a, b) zusammen mit den ganzen Zahlen x und y zu bestimmen, deren Existenz durch die Bézout-Identität garantiert wird.

Sehen wir uns nun an, wie wir diese Theorie nutzen können, um den multiplikativen Kehrwert von a modulo m zu finden:

1. Erinnere dich daran, dass wir davon ausgehen, dass a und m teilerfremd sind, also wissen wir, dass ggT(a,m) = 1.

2. Aus der Identität von Bézout wissen wir also, dass:

   a ∙ x + m ∙ y = 1

   für einige ganze Zahlen x und y. Wir verwenden den erweiterten euklidischen Algorithmus, um sie zu finden.

3. Jetzt können wir sehen, wie sie mit der multiplikativen modularen Inversen zusammenhängt. Wenden wir den Operator mod m auf beide Seiten der obigen Gleichung an, erhalten wir:

   a ∙ x + m ∙ y ≡ 1 (mod m).

4. Da jede Vielfachheit von m kongruent zu 0 modulo m ist, erhalten wir insbesondere m ∙ y ≡ 0 (mod m). Folglich können wir unsere Gleichung vereinfachen zu:

   a ∙ x ≡ 1 (mod m).

Aber hey, diese letzte Gleichung besagt, dass die durch den erweiterten Euklidischen Algorithmus gefundene ganze Zahl x genau die multiplikative Umkehrung von a modulo m ist! Das ist übrigens die Methode, die unser Modulare-Inversion-Rechner verwendet 😀

Der kleine Satz von Fermat

Bei der letzten Methode wird Fermats kleiner Satz verwendet. **Wir nehmen an, dass m eine Primzahl ist und a kein Vielfaches von m ist.

Fermats kleiner Lehrsatz.
Wenn m eine Primzahl ist und a nicht durch m teilbar ist, dann ist a^m-1 - 1 durch m teilbar.

Wir können die Behauptung des kleinen Satzes von Fermat so schreiben:

a^m-1 - 1 ≡ 1 mod m,

was wir wiederum umschreiben können als

a ∙ a^m-2 - 1 ≡ 1 mod m.

Diese Gleichung besagt, dass der modulare Kehrwert von a modulo m gleich a^m-2 ist.

Die Anweisung zur Verwendung des Rechners ist ganz einfach:

1. Wähle den Typ der modularen Umkehrung, den du finden möchtest:

• Modulare multiplikative Inverse; oder
• Modulare additive Inverse.

2. Gib die Koeffizienten der Gleichung ein, die du lösen möchtest.
3. Unser Rechner zeigt dir sofort die Lösung zusammen mit einer kurzen Erklärung an.