Modulo und Restklassen: Rechnen im Kreis

Kurz: Der Modulo-Operator liefert den Rest einer Division; er steckt in Uhrzeiten, Wochentagen, Hashfunktionen, Prüfziffern, Verschlüsselung und überall, wo etwas im Kreis läuft.

Genauer: 17 mod 5 = 2, weil 17 = 3·5 + 2. Zahlen, die denselben Rest haben, gehören zur gleichen Restklasse: Man „rechnet im Kreis“ wie auf der Uhr (14 Uhr ≙ 2 Uhr mod 12).

Im Detail

Grundlagen

• Notation: a mod n (mathematisch) bzw. a % n (Programmiersprachen).
• Beispiele: 10 % 3 = 1, 24 % 12 = 0, 7 % 10 = 7.
• Gerade/ungerade: n % 2. Teilbarkeit: n % k == 0.
• Rechenregeln: (a + b) mod n = ((a mod n) + (b mod n)) mod n, entsprechend für Multiplikation; so bleiben Zwischenergebnisse klein (wichtig bei Überlauf und Kryptografie).
• Negative Zahlen: -1 % 5 ist in Python 4, in C/Java/JavaScript −1 (Vorzeichen des Dividenden)! Für „echten“ Modulo ((a % n) + n) % n.

Anwendungen im Alltag

• Uhr/Kalender: Stunden mod 12/24; Wochentag nach k Tagen: (heute + k) % 7; Zeitzonen (mod 24).
• Zyklische Puffer (Ringpuffer): index = (index + 1) % größe; Spiele: Bildschirm-Umlauf (Pac-Man), Animationen, Runden.
• FizzBuzz, jedes n-te Element, Schachbrettmuster ((x + y) % 2).
• Verteilung: hash(key) % Anzahl_Server (Lastverteilung, Hashtabellen); Consistent Hashing löst das Umverteilungsproblem.
• Paginierung, Karussell, Caesar-Chiffre: (buchstabe + schlüssel) % 26.

Prüfziffern und Kryptografie

• IBAN: Prüfziffer über mod 97; ISBN-13, EAN/Barcode (Gewichtete Summe mod 10), Kreditkarten (Luhn-Algorithmus, mod 10): erkennen Tippfehler.
• Zufall: Lineare Kongruenzgeneratoren x' = (a·x + c) mod m.
• RSA/Diffie-Hellman: Potenzen modulo einer großen Zahl; schnelle modulare Exponentiation (Square-and-Multiply). Modulares Inverses (a·x ≡ 1 mod n) via erweiterten euklidischen Algorithmus.
• Hash-Prüfsummen, CRC (Rechnen in Körpern).

Typische Fehler und Prüfungstipps

• Off-by-one bei 0- vs. 1-basierten Zählungen (Monate/Wochentage: (x − 1) % 12 + 1).
• Division durch 0: % 0 Fehler.
• Gleitkomma-Modulo (fmod) hat Rundungsfragen.
• Vorzeichen je Sprache.
• Prüfung: Rest bestimmen, Wochentag berechnen, Prüfziffer nachrechnen, Programme mit % lesen.
• Üben: Zahlen in Restklassen-Tabellen (Addition/Multiplikation mod 5/7) aufschreiben; die Struktur wird sichtbar.

Siehe auch: Primzahlen und Sieb, Euklidischer Algorithmus, Hashmap, IBAN und SEPA