Modulo-Rechner: Rest bei Division berechnen (mod)

Die Modulo-Operation berechnet den Rest bei der ganzzahligen Division zweier Zahlen. Wenn du 17 durch 5 teilst, ergibt das 3 mit einem Rest von 2: 17 = 3 * 5 + 2. Genau diese 2 ist das Ergebnis von 17 mod 5.

Mathematisch ausdrueckt: Fuer den Dividend a und den Modul n sucht die Operation den Quotienten q und den Rest r, sodass a = q * n + r gilt. Der Rest ist dabei immer kleiner als der Modul.

Diese Division mit Rest, auch Euklidische Division genannt, ist eines der aeltesten mathematischen Verfahren und bildet die Grundlage fuer Kryptografie, Pruefsummen und Kalenderberbechnungen.

Im Alltag begegnet sie jedem, der Uhrzeiten berechnet: 15 Uhr plus 10 Stunden ergibt (15 + 10) mod 24 = 1 Uhr morgens. Der Rechner zeigt neben dem Rest auch den Quotienten und den vollstaendigen Rechenweg an.

Bei positiven Zahlen liefern beide Konventionen dasselbe Ergebnis. Der Unterschied zeigt sich erst bei negativen Dividenden.

Die floored-Variante (mathematische Konvention) verwendet den abgerundeten Quotienten (floor) und liefert immer einen Rest zwischen 0 und n-1. Beispiel: -17 mod 5 ergibt in der floored-Variante 3, weil floor(-17/5) = -4 und -17 - (-4)*5 = 3.

Die truncated-Variante (Programmiersprachen-Konvention) verwendet den gegen null gerundeten Quotienten (trunc) und liefert einen Rest mit dem Vorzeichen des Dividenden.

Beispiel: -17 mod 5 ergibt in der truncated-Variante -2, weil trunc(-17/5) = -3 und -17 - (-3)*5 = -2. In C, Java und JavaScript verwendet der Prozent-Operator die truncated-Variante, waehrend Python den floored-Modulo nutzt.

Der Rechner zeigt beide Ergebnisse nebeneinander, damit du die richtige Variante fuer deinen Anwendungsfall ablesen kannst.

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

Fuer den Modul n gibt es genau n Restklassen, von [0]_n bis [n-1]_n. Diese Restklassen bilden einen algebraischen Ring, in dem sich addieren und multiplizieren laesst, ohne die eigentlichen Zahlen zu kennen.

In der Praxis sind Restklassen die Grundlage von Pruefsummenverfahren: Die ISBN-Pruefziffer nutzt Modulo 11, die IBAN-Pruefung Modulo 97, und die EAN-Pruefziffer Modulo 10. Auch Wochentage sind Restklassen modulo 7.

Der Rechner gibt die Restklasse des Ergebnisses direkt aus, damit du siehst, in welcher aequivalenzklasse der Dividend liegt.

Die modulare Potenz berechnet a^k mod n, also den Rest der k-ten Potenz von a bei Division durch n. Direkt ausrechnen ist bei grossen Exponenten unpraktisch, weil die Zwischenergebnisse astronomisch gross werden.

Stattdessen verwendet der Rechner das Square-and-Multiply-Verfahren: Der Exponent wird binaer zerlegt, und in jedem Schritt wird entweder nur quadriert oder quadriert und multipliziert, wobei nach jedem Schritt der Rest modulo n genommen wird.

Dadurch bleiben alle Zwischenergebnisse kleiner als n*n. Beispiel: 7^11 mod 13 = 2, obwohl 7^11 fast zwei Milliarden betraegt.

In der Kryptografie ist modulare Potenz die zentrale Operation: RSA-Verschluesselung berechnet c = m^e mod n, und die Entschluesselung m = c^d mod n.

Auch der Diffie-Hellman-Schluesselaustausch und digitale Signaturen basieren auf modularer Exponentiation.

Der Prozent-Operator (%) in C, C++, Java, JavaScript und C# verwendet die truncated-Konvention: Der Quotient wird gegen null gerundet, und der Rest uebernimmt das Vorzeichen des Dividenden.

Python verwendet dagegen die floored-Konvention: Der Quotient wird abgerundet, und der Rest ist immer nicht-negativ bei positivem Modul. Fuer -17 % 5 liefert JavaScript also -2, waehrend Python 3 ausgibt.

Beide Ergebnisse sind mathematisch korrekt, sie definieren nur den Rest unterschiedlich. Um in JavaScript den floored-Rest zu erhalten, kannst du die Formel ((a % n) + n) % n verwenden.

Der Rechner zeigt beide Varianten nebeneinander, sodass du das Ergebnis deiner Programmiersprache sofort gegenchecken kannst, ohne die Konvention nachschlagen zu muessen.

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

Der Rechner gibt einen Teilbarkeitshinweis aus, der genau diese Pruefung durchfuehrt. Teilbarkeit per Modulo ist in der Praxis allgegenwaertig: Die Schaltjahrregel prueft, ob ein Jahr durch 4, 100 und 400 teilbar ist.

Die Pruefung gerader Zahlen entspricht n mod 2 == 0. Pruefsummen wie ISBN, IBAN und Personalausweisnummer nutzen Teilbarkeitspruefungen durch spezifische Module.

Auch in der Programmierung dient der Modulo-Test als schnelle Moeglichkeit, Schleifendurchlaeufe zu steuern, etwa wenn jede dritte Zeile einer Tabelle farblich hervorgehoben werden soll.

Die Uhr ist das bekannteste Alltagsbeispiel fuer modulare Arithmetik. Uhrzeiten rechnen modulo 12 oder modulo 24: 15 Uhr plus 10 Stunden ergibt (15 + 10) mod 24 = 1 Uhr morgens.

Wochentage rechnen modulo 7: Wenn heute Mittwoch (Tag 3) ist, dann ist in 10 Tagen (3 + 10) mod 7 = 6, also Samstag. Auch Monate lassen sich mit Modulo 12 berechnen.

In all diesen Faellen laeuft die Zaehlung periodisch ueber eine Obergrenze hinaus und beginnt wieder von vorn.

Mathematisch ist das genau die Restklassenarithmetik: Die Zeiger einer Uhr bewegen sich im Ring Z/12Z (12-Stunden-Format) oder Z/24Z (24-Stunden-Format).

Wer Modulo versteht, versteht auch, warum die Aussage 14 Uhr ist dasselbe wie 2 Uhr korrekt ist: Beide Werte liegen in derselben Restklasse modulo 12.

Der einfache Rest a mod n laesst sich fuer beliebig grosse Zahlen berechnen, solange die Sprache oder der Rechner die Zahlendarstellung beherrscht.

Bei der modularen Potenz ist das Square-and-Multiply-Verfahren entscheidend: Statt zuerst die riesige Potenz a^k auszurechnen und dann den Rest zu nehmen, wird nach jedem Schritt reduziert. Dadurch uebersteigt kein Zwischenergebnis n*n.

Fuer kryptografische Anwendungen mit 2048-Bit-Schluesseln nutzen Bibliotheken Arbitrary-Precision-Arithmetik, die prinzipiell genauso funktioniert, nur mit sehr grossen Modulen.

Der Rechner im Browser arbeitet mit JavaScript-Ganzzahlen und liefert exakte Ergebnisse, solange Dividend, Modul und Potenz im sicheren Ganzzahlbereich liegen (bis 2^53 - 1).

Fuer Schul- und Alltagsberechnungen reicht das voellig aus, fuer echte Kryptografie wuerden spezielle Bibliotheken benoetigt.