Modulo and residue classes: calculating in a circle

In short: The modulo operator returns the remainder of a division; it appears in clock times, weekdays, hash functions, check digits, encryption and everywhere something runs in a circle.

In more detail: 17 mod 5 = 2, because 17 = 3·5 + 2. Numbers with the same remainder belong to the same residue class: you “calculate in a circle” like on a clock (14:00 ≙ 2:00 mod 12).

In Depth

Basics

• Notation: a mod n (mathematical) or a % n (programming languages).
• Examples: 10 % 3 = 1, 24 % 12 = 0, 7 % 10 = 7.
• Even/odd: n % 2. Divisibility: n % k == 0.
• Rules: (a + b) mod n = ((a mod n) + (b mod n)) mod n, likewise for multiplication; this keeps intermediate results small (important with overflow and cryptography).
• Negative numbers: -1 % 5 is 4 in Python, −1 in C/Java/JavaScript (sign of the dividend)! For a “true” modulo ((a % n) + n) % n.

Everyday applications

• Clock/calendar: hours mod 12/24; weekday after k days: (today + k) % 7; time zones (mod 24).
• Circular buffers (ring buffer): index = (index + 1) % size; games: screen wrap-around (Pac-Man), animations, rounds.
• FizzBuzz, every n-th element, chessboard pattern ((x + y) % 2).
• Distribution: hash(key) % number_of_servers (load distribution, hash tables); consistent hashing solves the redistribution problem.
• Pagination, carousel, Caesar cipher: (letter + key) % 26.

Check digits and cryptography

• IBAN: check digits via mod 97; ISBN-13, EAN/barcode (weighted sum mod 10), credit cards (Luhn algorithm, mod 10): detect typing errors.
• Randomness: linear congruential generators x' = (a·x + c) mod m.
• RSA/Diffie-Hellman: powers modulo a large number; fast modular exponentiation (square-and-multiply). Modular inverse (a·x ≡ 1 mod n) via extended Euclidean algorithm.
• Hash checksums, CRC (calculating in fields).

Typical mistakes and exam tips

• Off-by-one with 0- vs. 1-based counting (months/weekdays: (x − 1) % 12 + 1).
• Division by 0: % 0 error.
• Floating-point modulo (fmod) has rounding issues.
• Sign depends on the language.
• Exam: determine the remainder, calculate a weekday, recompute a check digit, read programs with %.
• Practise: write residue tables (addition/multiplication mod 5/7); the structure becomes visible.

See also: Primes and sieve, Euclidean algorithm, Hashmap, IBAN and SEPA