Modulo-Rechner: Rest bei Division berechnen (mod)

Modulo ist der Rest, der bei der ganzzahligen Division zweier Zahlen übrig bleibt. Teilst du 17 durch 5, ergibt das 3 mit Rest 2: 17 = 3 * 5 + 2. Genau diese 2 ist das Ergebnis von 17 mod 5.

Das Zeichen für Modulo ist in der Mathematik meist „mod“ (17 mod 5), in Programmiersprachen der Prozent-Operator (17 % 5).

Formal sucht die Operation für den Dividend a und den Modul n den Quotienten q und den Rest r, sodass a = q * n + r gilt, wobei der Rest immer kleiner als der Modul bleibt.

Diese Division mit Rest, auch Euklidische Division genannt, ist eines der ältesten Rechenverfahren und bildet die Grundlage für Kryptografie, Prüfsummen und Kalenderberechnungen.

Achte darauf, dass der Modul n dabei stets größer als 0 sein muss, sonst ist die Operation nicht definiert. Der Rechner oben zeigt dir zu jeder Eingabe sofort Rest, Quotient und den vollständigen Rechenweg an.

Modulo berechnest du, indem du zuerst den Quotienten q durch Abrunden von a/n bestimmst und dann r = a - q * n rechnest. Beispiel: 17 mod 5 ergibt q = floor(17/5) = 3, also r = 17 - 3 * 5 = 2.

Ein zweites Beispiel mit größeren Zahlen: 24 mod 5 ergibt q = 4, also r = 24 - 4 * 5 = 4. Trage dazu den Dividenden und den Modul in die Felder oben ein, dann erscheint der komplette Rechenweg automatisch.

Wichtig ist die Reihenfolge: Erst den Quotienten runden, dann multiplizieren und subtrahieren, niemals den Rest raten. Bei handschriftlicher Rechnung hilft die kleine Einmaleins-Reihe des Moduls, um den passenden Quotienten schnell zu finden.

Der Rest liegt bei positiven Zahlen immer zwischen 0 und n minus 1, hier also zwischen 0 und 4.

Bei negativen Dividenden hängt das Ergebnis von der gewählten Konvention ab.

Die floored-Variante (mathematische Konvention) rundet den Quotienten ab und liefert immer einen Rest zwischen 0 und n minus 1: -17 mod 5 ergibt hier 3, weil floor(-17/5) = -4 und -17 - (-4) * 5 = 3.

Die truncated-Variante (Programmiersprachen-Konvention) rundet den Quotienten gegen null und der Rest übernimmt das Vorzeichen des Dividenden: -17 mod 5 ergibt dort -2, weil trunc(-17/5) = -3 und -17 - (-3) * 5 = -2.

Beide Ergebnisse sind mathematisch korrekt, sie definieren den Rest nur unterschiedlich.

Wähle im Rechner oben die Konvention passend zu deinem Anwendungsfall aus, etwa floored für Schulmathematik und truncated, wenn du ein Ergebnis aus C, Java oder JavaScript nachrechnen willst.

Beide Varianten werden dir nebeneinander angezeigt, damit du sie direkt vergleichen kannst.

Für Modulo gelten feste Rechenregeln, die große Zwischenergebnisse vermeiden: (a + b) mod n = ((a mod n) + (b mod n)) mod n und (a * b) mod n = ((a mod n) * (b mod n)) mod n.

Beispiel Addition: (7 + 8) mod 5 = 15 mod 5 = 0, und ebenso (7 mod 5 + 8 mod 5) mod 5 = (2 + 3) mod 5 = 0. Beispiel Multiplikation: (6 * 4) mod 5 = 24 mod 5 = 4, und ebenso (6 mod 5 * 4 mod 5) mod 5 = (1 * 4) mod 5 = 4.

Diese Regeln stecken hinter dem Square-and-Multiply-Verfahren, mit dem der Rechner die modulare Potenz berechnet, ohne riesige Zwischenwerte zu erzeugen.

Beachte, dass diese Kürzung bei der Division nicht in gleicher Form gilt: a/b mod n lässt sich nicht einfach über (a mod n)/(b mod n) bestimmen, dafür braucht es das modulare Inverse.

Eine Restklasse [r]_n ist die Menge aller ganzen Zahlen, die bei Division durch n denselben Rest r ergeben. Die Restklasse [2]_5 umfasst zum Beispiel ..., -8, -3, 2, 7, 12, 17, 22, ..., also alle Zahlen der Form 5k + 2.

Zwei Zahlen mit demselben Rest heißen kongruent modulo n, geschrieben als a ≡ b (mod n): Da sowohl 17 mod 5 als auch 22 mod 5 den Rest 2 ergeben, gilt 17 ≡ 22 (mod 5).

Für den Modul n gibt es genau n Restklassen, von [0]_n bis [n-1]_n, die einen algebraischen Ring bilden.

In der Praxis stecken Restklassen hinter Prüfsummenverfahren wie der ISBN-Prüfziffer (Modulo 11) und der IBAN-Prüfung (Modulo 97), aber auch hinter der Wochentagsberechnung modulo 7.

Der Rechner gibt dir die Restklasse deines Ergebnisses direkt aus, sodass du die Äquivalenzklasse sofort ablesen kannst.

Excel berechnet Modulo mit der Funktion MOD(Zahl, Divisor), die genau wie die mathematische floored-Konvention arbeitet.

MOD(17, 5) liefert 2, exakt das gleiche Ergebnis wie im Rechner oben bei Dividend 17 und Modul 5 in der Konvention „Mathematisch (floored)“.

Bei negativen Zahlen zeigt sich der Unterschied zur Programmierwelt deutlich: MOD(-17, 5) ergibt in Excel 3, nicht -2, weil Excel wie Python der floored-Konvention folgt und nicht dem truncated-Verhalten von VBA, C oder Java.

Trage einen negativen Dividenden im Rechner ein und vergleiche das floored-Ergebnis direkt mit deiner Excel-Tabelle.

Ein häufiger Excel-Fehler ist die Verwechslung von MOD mit der ähnlich klingenden ganzzahligen Division QUOTIENT(Zahl, Divisor), die stattdessen den Quotienten statt des Rests liefert.

Beide Funktionen zusammen entsprechen genau der Grundformel a = q * n + r, die der Rechner als Rechenweg ausgibt.

Der Grund liegt in zwei verschiedenen Konventionen für negative Zahlen.

Java, JavaScript, C und C++ verwenden bei ihrem Prozent-Operator die truncated-Konvention: Der Quotient wird gegen null gerundet, der Rest übernimmt das Vorzeichen des Dividenden. Für -17 % 5 liefern alle vier Sprachen daher -2.

Python dagegen verwendet die floored-Konvention und gibt für -17 % 5 den Wert 3 aus, weil der Quotient abgerundet und der Rest immer nicht-negativ gehalten wird.

Um in JavaScript, Java, C oder C++ den floored-Rest zu erhalten, hilft die Formel ((a % n) + n) % n.

Der Rechner oben zeigt beide Konventionen gleichzeitig an und benennt sie explizit, sodass du das Ergebnis deiner jeweiligen Programmiersprache sofort gegenchecken kannst, ohne die Sprachdokumentation nachzuschlagen.

Bei positiven Zahlen liefern übrigens alle genannten Sprachen dasselbe Ergebnis, der Unterschied zeigt sich ausschließlich bei negativem Dividenden.

Die modulare Potenz berechnet a^k mod n, also den Rest der k-ten Potenz von a bei Division durch n. Direktes Ausrechnen scheitert bei großen Exponenten, weil die Zwischenwerte astronomisch groß werden.

Der Rechner nutzt deshalb das Square-and-Multiply-Verfahren: Der Exponent wird binär zerlegt, in jedem Schritt wird quadriert und bei Bedarf zusätzlich multipliziert, wobei nach jedem Schritt der Rest modulo n genommen wird.

Beispiel: 7^11 mod 13 ergibt nur 2, obwohl 7^11 rechnerisch fast zwei Milliarden beträgt (1.977.326.743). Trage im optionalen Exponentenfeld einen Wert ein, um dieses Verfahren live zu sehen.

In der Kryptografie ist modulare Potenz die zentrale Operation: RSA-Verschlüsselung berechnet c = m^e mod n und die Entschlüsselung m = c^d mod n auf genau diese Weise.

Ohne dieses Verfahren wären solche Berechnungen mit heutigen Schlüssellängen praktisch nicht durchführbar.

Eine Zahl a ist genau dann durch n teilbar, wenn a mod n gleich 0 ist. Beispiel: 15 mod 5 ergibt 0, also ist 15 durch 5 teilbar. 17 mod 5 ergibt dagegen 2, also ist 17 nicht durch 5 teilbar.

Der Rechner gibt bei jeder Eingabe automatisch einen Teilbarkeitshinweis aus, der genau diese Prüfung durchführt.

Teilbarkeit per Modulo ist in der Praxis allgegenwärtig: Die Schaltjahrregel prüft, ob ein Jahr durch 4, 100 und 400 teilbar ist, gerade Zahlen erkennst du an n mod 2 = 0.

Achte darauf, dass diese Prüfung unabhängig von der gewählten Konvention (floored oder truncated) immer dasselbe Ergebnis liefert, weil ein Rest von 0 in beiden Varianten identisch ist.

In der Programmierung dient der Modulo-Test außerdem als schnelle Möglichkeit, Schleifendurchläufe zu steuern, etwa wenn jede dritte Zeile einer Liste hervorgehoben werden soll.