So verwenden Sie es
- Wählen Sie die Rechenart: a mod n, die Inverse, eine Potenz oder den Chinesischen Restsatz.
- Tragen Sie die Zahl a, den Exponenten e und den Modul n dort ein, wo sie verlangt werden, oder eine Kongruenz je Zeile unter Kongruenzen (eine je Zeile).
- Lesen Sie das Ergebnis ab. Bei der Inverse zeigt das Feld Prüfung, ob sie existiert.
- Gehen Sie unter So wird es berechnet durch. Die Tabellen zeigen die Zeilen des euklidischen Algorithmus oder die Binärziffern.
Reste, Inverse und Potenzen
Der Rest von a modulo n ist die Zahl r mit 0 ≤ r < n und a = q·n + r. Daher ist a mod n nie negativ: −17 mod 5 ist 3, denn −17 = (−4)·5 + 3. Eine Inverse von a modulo n ist eine Zahl x mit a·x ≡ 1 (mod n). Sie existiert genau dann, wenn ggT(a; n) = 1 ist, und der erweiterte euklidische Algorithmus findet sie. Eine Potenz a^e mod n berechnet man mit Quadrieren und Multiplizieren, das pro Binärziffer von e einmal quadriert.
a mod n = a − n·⌊a ÷ n⌋
Ist s·a + t·n = 1, so ist a⁻¹ ≡ s (mod n)- Viele Taschenrechner liefern für −17 mod 5 den Wert −2, den Rest der abgeschnittenen Division. Das ist nicht der Rest im Sinne der Restklassen, der immer zwischen 0 und n − 1 liegt.
- Eine Potenz mit negativem Exponenten verwendet die Inverse von a und existiert daher nur, wenn ggT(a; n) = 1 ist.
- Die Tabelle des euklidischen Algorithmus und die Binärtabelle zeigen jede Zwischenzahl, sodass sich der Rechenweg von Hand nachprüfen lässt.
Der Chinesische Restsatz und was nicht abgedeckt ist
Der Chinesische Restsatz findet eine Zahl x, die bei Division durch jeden Modul mᵢ den Rest rᵢ lässt, für jede Kongruenz eines Systems. Sind die Module paarweise teilerfremd, gibt es genau eine Lösung modulo ihres Produkts. Sind sie es nicht, müssen die Reste modulo des ggT der Module übereinstimmen, sonst hat das System keine Lösung.
- Sehr große Exponenten mit mehr als 64 Binärziffern werden abgelehnt, damit der Rechenweg lesbar bleibt.
- Kongruenzen mit einer anderen Variablen als x, Polynomkongruenzen und modulare Quadratwurzeln werden nicht behandelt.
- Der Rechner rechnet nur mit ganzen Zahlen. Eine Dezimalzahl wird abgelehnt.
Rechenbeispiel: 4¹³ mod 497 und die anderen Rechenarten
Der Exponent 13 lautet im Binärsystem 1101. Beginnend mit 1 und quadrierend bei jeder Ziffer, mit einer Multiplikation mit 4 bei jeder 1, ergeben sich die Werte 4, 64, 120 und dann 445, also ist 4¹³ mod 497 = 445. Dasselbe Verfahren läuft im Rechner mit seiner Tabelle der Ziffern ab.
Die anderen Beispiele: −17 mod 5 = 3. Die Inverse von 4 modulo 7 ist 2, denn 4 × 2 = 8 ≡ 1. Und x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) hat die Lösung x ≡ 23 (mod 105).
| Frage | Antwort |
|---|---|
| 4^13 mod 497 | 445 |
| −17 mod 5 | 3 |
| Inverse von 4 modulo 7 | 2 |
| x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7) | x ≡ 23 (mod 105) |
Häufig gestellte Fragen
Warum ist −17 mod 5 gleich 3 und nicht −2?
Der Rest liegt immer zwischen 0 und n − 1 und ist deshalb nie negativ. Da −17 = (−4) × 5 + 3 ist, ist der Rest 3. Viele Taschenrechner zeigen −2. Das ist der Rest der abgeschnittenen Division und nicht der Rest modulo n.
Wann hat eine Zahl eine Inverse modulo n?
Wenn der größte gemeinsame Teiler von Zahl und n gleich 1 ist. Zum Beispiel hat 4 modulo 7 die Inverse 2, aber modulo 6 hat 4 keine, weil ggT(4; 6) = 2 ist.
Warum verwendet die Potenz Quadrate statt wiederholter Multiplikation?
Das Quadrieren mit Rest bei jeder Binärziffer hält jede Zahl klein. Bei 4¹³ ist der größte Zwischenwert 484 × 4 = 1936, statt einer Zahl mit rund 8 Stellen, wie sie ein langes Produkt ergeben würde.
Was ist, wenn die Kongruenzen Module mit einem gemeinsamen Teiler haben?
Das System kann trotzdem eine Lösung haben. Die Reste müssen modulo des ggT der beiden Module übereinstimmen: x ≡ 2 (mod 4) und x ≡ 8 (mod 6) stimmen überein, und die Lösung ist x ≡ 2 (mod 12).
Werden meine Zahlen an einen Server geschickt?
Nein. Die Berechnung läuft in Ihrem Browser, und nichts, was Sie eingeben, wird an uns übermittelt.
Quellen
- Wikipedia (englisch): Modular arithmetic, Restklassenarithmetik
- Wikipedia (englisch): Modular exponentiation, modulare Exponentiation
- Wikipedia (englisch): Extended Euclidean algorithm, erweiterter euklidischer Algorithmus
- Wikipedia (englisch): Chinese remainder theorem, Chinesischer Restsatz
Zahlen und Text zuletzt geprüft: Dienstag, 10. November 2026.