Modulo-Rechner

Was bedeutet Modulo berechnen?

Modulo beschreibt den Rest einer Division. Du teilst also eine Zahl durch einen Modul und schaust, was nach dem ganzzahligen Anteil übrig bleibt. Bei 23 mod 10 ist der Rest 3, weil 23 = 2 · 10 + 3. Die Schreibweise 23 ≡ 3 (mod 10) sagt: 23 gehört im Modul 10 zur gleichen Restklasse wie 3.

Das ist praktisch, wenn sich Werte zyklisch wiederholen. Uhrzeiten laufen nach 24 Stunden wieder von vorn los, Wochentage nach 7 Tagen. Deshalb passt Modulo gut zu Fragen wie “Welche Uhrzeit ist 22 Uhr + 5 Stunden?” Die Rechnung lautet (22 + 5) mod 24 = 3, also 3 Uhr.

Im Rechner wählst du oben die gewünschte Berechnung aus und gibst Zahl a, Modul n und bei Potenzen zusätzlich den Exponenten k ein.

Wie funktioniert die Rechnung im modulo rechner?

Die Grundidee lautet in Worten: Nimm von a so oft n weg, bis ein Rest bleibt, der im mathematischen Sinn zwischen 0 und |n| - 1 liegt. Als Formel: a mod n = a - n · ⌊a ÷ n⌋. Gleichwertig schreibt man a = q · n + r mit 0 ≤ r < |n|. Dabei ist q der ganzzahlige Quotient und r der Rest.

Ein einfaches Beispiel ist 17 mod 5. Der ganzzahlige Quotient ist 3. Der Rechenweg lautet:

• 17 = 3 · 5 + 2
• Der Rest ist 2
• Als Kongruenz: 17 ≡ 2 (mod 5)

Damit ist 17 nicht durch 5 teilbar, denn der Rest ist 2. Eine Division geht im Modulo-Sinn nur dann glatt auf, wenn der Rest 0 ist. Bei 1.000 mod 3 bleibt zum Beispiel 1 übrig, denn 1.000 = 333 · 3 + 1. Auch hier liegt keine Teilbarkeit durch 3 vor.

Modulo negative Zahlen: Mathematik und Programmiersprachen unterscheiden sich

Bei negativen Dividenden entsteht oft Verwirrung. Mathematisch wird der Rest meist so gewählt, dass er im positiven Bereich des Moduls liegt. Für -17 mod 5 ergibt sich daher 3. Der zugehörige Rechenweg ist -17 = (-4) · 5 + 3, also -17 ≡ 3 (mod 5).

Einige Programmiersprachen verwenden jedoch eine andere Konvention. In JavaScript, Java, C/C++ und PHP hat der Rest beim %-Operator das Vorzeichen von a. Deshalb kann dort bei -17 % 5 der Wert -2 herauskommen. Python, Excel REST() und Ruby liefern bei positivem Modul dagegen 3.

Das ist kein Rechenfehler, sondern eine Definitionsfrage. Für Mathematik, Zahlentheorie und Schulrechnung ist die euklidische Variante meist die passende. Wenn du Code schreibst oder Ergebnisse aus Programmiersprachen vergleichst, solltest du die verwendete Modulo-Konvention prüfen.

Modulare Potenz: aᵏ mod n ohne riesige Zwischenzahl

Bei einer modularen Potenz wird nicht erst die komplette Potenz ausgerechnet und danach geteilt. Stattdessen wird nach Zwischenschritten immer wieder der Rest modulo n genommen. Das hält die Zahlen klein und funktioniert auch bei großen Exponenten. Die Methode heißt schnelles Potenzieren oder Square-and-Multiply.

Ein Beispiel: 7^11 mod 13 ergibt 2. Der Exponent 11 wird binär als 1011 betrachtet. Nur bei Bit 1 wird die aktuelle Quadratpotenz in das Ergebnis einbezogen, nach jedem Schritt wird wieder modulo 13 gerechnet. Der Rechner zeigt dazu den Weg über 7^1, 7^2, 7^4 und 7^8.

Weitere Beispiele zeigen den gleichen Gedanken: 2^10 mod 7 ergibt 2, 5^11 mod 13 ergibt 8 und 12^20 mod 17 ergibt 13. Du brauchst die riesige Potenz also nicht vollständig hinzuschreiben, um den Rest zu bestimmen.

Modulares Inverses: Wann gibt es eine Zahl zum Zurückrechnen?

Ein modulares Inverses zu a modulo n ist eine Zahl, die mit a multipliziert den Rest 1 ergibt. Für 3 mod 11 ist das Inverse 4, denn 3 · 4 = 12 ≡ 1 (mod 11). Der Rechner verwendet dafür den erweiterten euklidischen Algorithmus.

Die Bedingung dahinter ist der ggT(a, n) = 1. Dann sind a und n teilerfremd, und ein Inverses existiert. Im Beispiel 7 mod 26 ist das Inverse 15. Der Rechenweg zeigt -11 · 7 + 3 · 26 = 1 und daraus 7 · 15 ≡ 1 (mod 26).

Auch größere Werte funktionieren nach demselben Prinzip. Für 17 mod 3.120 ist das modulare Inverse 2.753, denn 17 · 2.753 = 46.801 ≡ 1 (mod 3.120). Solche Rechnungen tauchen häufig in Kryptografie, Codierungen und Verfahren mit Restklassen auf.

Typische Fehler beim Rest berechnen vermeiden

Der häufigste Fehler ist, den Quotienten zu früh abzuschneiden, aber den Rest nicht zur gewählten Modulo-Definition passend zu bestimmen. Besonders bei negativen Zahlen musst du entscheiden, ob du das mathematische Ergebnis brauchst oder das Ergebnis einer bestimmten Programmiersprache vergleichst.

Weitere typische Stolperstellen:

• Verwechsle den Quotienten nicht mit dem Rest. Bei 100 mod 7 ist der Quotient 14, der Rest aber 2.
• Achte auf das Vorzeichen. Mathematisch gilt -17 mod 5 = 3, während JavaScript, Java und C den Rest -2 liefern können.
• Prüfe Teilbarkeit über den Rest. Ist der Rest 0, geht die Division ohne Rest auf. Bei 17 mod 5 bleibt 2, also keine Teilbarkeit.
• Bei Uhrzeiten und Wochentagen ist Modulo besonders passend, weil sich die Werte im Kreis wiederholen. Montag + 30 Tage ergibt über (1 + 30) mod 7 = 3 wieder Mittwoch.
• Bei IBAN-artigen Prüfungen können sehr große Zahlen auftreten. Entscheidend ist trotzdem nur der Rest, zum Beispiel bei mod 97 der Rest 1.