Modulo-Rechner: a mod n und Potenzen modulo n berechnen
MathematikTragen Sie die Zahl und den Teiler ein: Der Rechner nennt den Rest der Division (a mod n), den Quotienten und den Rest, den Programmiersprachen bei negativen Zahlen liefern. Im zweiten Modus berechnet er Potenzen modulo n.
Rechenweg
17 mod 5 = 2
- Teilen Sie 17 durch 5 und runden Sie den Quotienten nach unten: q = 3.
- Der Rest ist r = a − q · n = 17 − 3 · 5 = 2. Er ist nie negativ und kleiner als der Teiler 5.
- Eine Programmiersprache, die % mit dem Vorzeichen des Dividenden berechnet (C, Java, JavaScript), liefert 2.
Sobald alle Eingaben gültig sind, sehen Sie hier jeden Rechenschritt.
Formel
- a
- die Zahl, von der der Rest gesucht wird (Dividend), eine ganze Zahl, auch negativ
- n
- der Teiler oder Modul, eine ganze Zahl ab 1
- q
- der ganzzahlige Quotient, a / n nach unten gerundet
- r
- der Rest, immer mit 0 ≤ r < n
- b
- der Exponent beim Potenzieren, eine ganze Zahl ab 0
So funktioniert der Rechner
Der Modulo einer Zahl a bezüglich n ist der Rest der Division a : n. Zu jeder ganzen Zahl a und jedem positiven Teiler n gibt es genau einen Quotienten q und genau einen Rest r mit a = q · n + r und 0 ≤ r < n. Dieses r schreibt man a mod n. Beispiel: 17 = 5 · 3 + 2, also 17 mod 3 = 2, und 3 mod 3 = 0, weil 3 = 1 · 3 + 0 gilt. Den Quotienten q erhalten Sie, indem Sie a / n nach unten runden.
Bei negativen Zahlen bleibt der Rest in der Mathematik nicht-negativ: −8 mod 6 = 4, denn −8 = (−2) · 6 + 4. Programmiersprachen sind nicht einheitlich. C, Java, JavaScript und PHP geben dem Rest das Vorzeichen des Dividenden, deshalb liefert dort −8 % 6 den Wert −2. Python, Ruby und Excel rechnen mit dem mathematischen Rest. Der Rechner zeigt beide Werte. Aus dem Rest mit Vorzeichen erhalten Sie den mathematischen, indem Sie ((a % n) + n) % n bilden.
Zwei Zahlen mit demselben Rest heißen kongruent modulo n: 43 und −7 lassen beide den Rest 3 bei Division durch 5, man schreibt 43 ≡ −7 (mod 5). Mit Resten rechnen Sie wie mit Zahlen: Summen und Produkte dürfen Sie vorher modulo n verkleinern. Modulo steckt in vielen Aufgaben: Mit a mod 2 prüfen Sie, ob eine Zahl gerade ist, mit Sekunden mod 3600 den Rest seit der vollen Stunde, und Prüfziffern wie bei IBAN und ISBN beruhen darauf.
Im Modus Potenz modulo n berechnet der Rechner a^b mod n mit schnellem Potenzieren, also Quadrieren und Multiplizieren entlang der Binärstellen des Exponenten, und kürzt nach jedem Schritt modulo n. So bleiben alle Zwischenwerte klein. Damit jedes Produkt exakt bleibt, darf der Modul höchstens 94.000.000 betragen. In der Kryptografie, etwa bei RSA, sind solche Potenzen modulo n das tägliche Brot. Die Quadratzahlen und Potenzen selbst berechnet der Potenz-Rechner, den größten gemeinsamen Teiler der ggT-Rechner.
Zur Formel
Bei positivem Teiler ist der Rest der Mathematik immer null oder positiv und kleiner als n. Der Rechner bildet ihn aus dem Rest mit Vorzeichen a % n: Ist dieser negativ, addiert er n. Den Quotienten erhält er exakt als (a − r) / n. Für a ≥ 0 sind der mathematische Rest und der Rest mit Vorzeichen gleich.
Für Potenzen gilt a^b mod n = ((a mod n)^b) mod n. Beispiel: 7^100 mod 13: Es ist 7^12 ≡ 1 (mod 13), und 100 = 12 · 8 + 4, also 7^100 ≡ 7^4 = 2401 ≡ 9 (mod 13), denn 2401 = 184 · 13 + 9. Der Rechner kommt ohne diesen Satz aus und rechnet Schritt für Schritt mit Zwischenwerten kleiner als n.
Rechenbeispiel
Was ist −8 mod 6?
- Teilen Sie −8 durch 6: −8 / 6 = −1,33…, nach unten gerundet ist q = (-2).
- Der Rest ist −8 − (-2) · 6 = −8 + 12 = 4. Er liegt zwischen 0 und 5, also ist −8 mod 6 = 4.
- Java, C und JavaScript geben für −8 % 6 dagegen (-2) zurück, den Rest mit dem Vorzeichen des Dividenden. Addieren Sie n, erhalten Sie den mathematischen Rest: −2 + 6 = 4.
(-8) mod 6 ergibt 4, denn (-8) = (-2) · 6 + 4.
Beispiel in den Rechner übernehmenHäufige Fragen
Wie rechne ich Mod?
a mod n ist der Rest der Division a : n. Teilen Sie a durch n, runden Sie den Quotienten nach unten auf eine ganze Zahl q und bilden Sie r = a − q · n. Für 17 mod 5 ist q = 3 und r = 17 − 15 = 2. Im Rechner tragen Sie a und n ein und lesen den Rest ab.
Wie rechnet man Modulo mit Taschenrechner?
Teilen Sie a durch n und runden Sie das Ergebnis nach unten auf eine ganze Zahl q. Bei a ≥ 0 ist das die Zahl vor dem Komma, bei negativem a nur, wenn die Division aufgeht: −8 / 6 = −1,33… ergibt q = −2, nicht −1. Dann ziehen Sie q · n von a ab: 17 / 5 = 3,4, also q = 3 und der Rest 17 − 3 · 5 = 2, und −8 − (−2) · 6 = 4. Wer den Nachkommateil mal n nimmt (0,4 · 5 = 2), kann durch Rundungsfehler danebenliegen. Die Subtraktion ist sicherer.
Wie rechne ich mit Modulo?
Mit Resten rechnen Sie wie mit Zahlen und kürzen modulo n: (a + b) mod n = ((a mod n) + (b mod n)) mod n, ebenso beim Produkt. Beispiel mit n = 5: (17 · 4) mod 5 = 68 mod 5 = 3, und (17 mod 5) · (4 mod 5) = 2 · 4 = 8, 8 mod 5 = 3. Das hält die Zahlen klein.
Was bedeutet „mod“ in der Mathematik?
„mod“ steht für Modulo und liefert den Rest einer Division mit Rest. a mod n = r heißt: a = q · n + r mit 0 ≤ r < n. 17 mod 3 = 2, weil 17 = 5 · 3 + 2. Auch die Schreibweise a ≡ b (mod n) nutzt das Wort: a und b sind kongruent modulo n, wenn sie denselben Rest lassen.
Was ist −8 mod 6?
In der Mathematik ist −8 mod 6 = 4, denn −8 = (−2) · 6 + 4 mit einem Rest zwischen 0 und 5. Programmiersprachen wie C, Java, JavaScript und PHP liefern für −8 % 6 dagegen −2, den Rest mit dem Vorzeichen des Dividenden. Python, Ruby und Excel liefern 4.
Warum liefert % in Java oder JavaScript bei negativen Zahlen etwas anderes?
Weil diese Sprachen den Rest einer abgeschnittenen Division berechnen: Er hat das Vorzeichen des Dividenden. Mathematisch und in Python bleibt der Rest nicht-negativ. Für a ≥ 0 stimmen beide überein. Den mathematischen Rest erhalten Sie mit ((a % n) + n) % n.
Wie prüfe ich, ob eine Zahl gerade ist?
Mit Modulo 2: Ist a mod 2 = 0, ist a gerade, bei 1 ungerade. 2026 mod 2 = 0, also ist 2026 gerade, 2027 mod 2 = 1, also ungerade. Das funktioniert auch bei negativen Zahlen, wenn Sie den mathematischen Rest nehmen.
Was bedeutet kongruent modulo n?
Zwei ganze Zahlen a und b sind kongruent modulo n, wenn sie denselben Rest lassen oder sich um ein Vielfaches von n unterscheiden. 43 und −7 lassen beide den Rest 3 bei Division durch 5, ihre Differenz 50 ist durch 5 teilbar. Man schreibt 43 ≡ −7 (mod 5).
Wofür braucht man Modulo im Alltag und in der Technik?
Etwa für die Uhrzeit: 5.000 Sekunden mod 3600 = 1.400, das sind 23 Minuten und 20 Sekunden seit der vollen Stunde. Dazu für Prüfziffern bei IBAN und ISBN, für Gerade-ungerade-Tests, für Wiederholungen alle k Schritte in Programmen und für Kryptografie wie RSA.
Wie berechnet man eine Potenz modulo n?
Mit schnellem Potenzieren: Sie quadrieren die Basis wiederholt und multiplizieren die passenden Potenzen, nach jedem Schritt mod n. So braucht 7^100 mod 13 nur wenige kleine Rechnungen. Das Ergebnis ist 9. Im Rechner wählen Sie „Potenz modulo n“ und tragen Basis, Exponent und Modul ein.
Was ist eine Zahl mod 1?
Immer 0. Für n = 1 verlangt 0 ≤ r < 1, dass der Rest 0 ist, und jede ganze Zahl a ist ein Vielfaches von 1: 999 = 999 · 1 + 0. Auch jede Potenz mod 1 ist 0.
Warum darf der Teiler nicht 0 sein?
Eine Division durch 0 ist nicht definiert, also gibt es auch keinen Rest. Der Rechner verlangt deshalb einen Teiler von mindestens 1. Negative Teiler lässt er nicht zu, denn bei ihnen gibt es mehrere gebräuchliche Festlegungen für das Vorzeichen des Rests.
Wie groß dürfen die Zahlen sein?
Im Modus „Rest“ darf a zwischen −1.000.000.000.000 und 1.000.000.000.000 liegen, der Teiler bis 1.000.000.000.000. Bei Potenzen darf der Modul höchstens 94.000.000 betragen, die Basis bis ±1.000.000.000 und der Exponent bis 1.000.000.000.000. Dann bleibt jede Zwischenrechnung exakt.
- Division mit Rest: Definition mit 0 ≤ r < |m|, Modulo, negative Zahlen und die Varianten in Programmiersprachen, Kongruenz, Anwendungen (Wikipedia)
- Kongruenz (Zahlentheorie): kongruent modulo m, Restklassen (Wikipedia)
- Schnelle Exponentiation: Potenzieren durch Quadrieren und Multiplizieren (Wikipedia)