Modular Arithmetic: Remainders, Rules & Applications

Expression

Meaning

n mod 2 = 0

Even number test

n mod 10

Last digit

h mod 24

Clock wrap-around

day mod 7

Weekday cycle

n mod 9

Digital root / divisibility by 9

a⁻¹ mod m

RSA cryptography, fraction in mod arithmetic

Key Takeaways

Definition: 17 mod 5 = 2 (17 = 3×5 + 2) — the remainder, always in [0, n−1]

Clock arithmetic: 14:00 + 10h = 24 mod 12 → 0 (midnight) — clocks are mod 12

Distribution rules: mod survives +, −, × — apply before or after, same answer

Cycles: powers mod n repeat — exploit the cycle instead of computing 3¹⁰⁰

Core answer: a mod n is the remainder when a is divided by n: 17 mod 5 = 2. It's clock arithmetic — 22:00 plus 5 hours is (22 + 5) mod 24 = 3 AM. Modular arithmetic powers week cycles, checksums (ID card last digit), hash tables, and all of modern public-key cryptography.

The clock intuition

Arithmetic "mod 12" is clock arithmetic: 9 + 8 = 17 ≡ 5 (mod 12). Two numbers are congruent mod n when they differ by a multiple of n: 17 ≡ 5 ≡ 29 (mod 12). You may add, subtract, and multiply freely then reduce — (25 × 34) mod 7 = (4 × 6) mod 7 = 24 mod 7 = 3.

Everyday uses

Application	Modulus	Example
12/24-hour clock	12 / 24	22 + 5 ≡ 3 (mod 24)
Weekday cycles	7	100 days from Monday = Thursday (100 mod 7 = 2)
ID card check digit	11	GB 11643 weighted sum mod 11
ISBN-10	11	last digit validates the rest
Credit card (Luhn)	10	catches any single-digit typo
Hash tables	table size	key mod m picks the bucket

Worked examples

Example 1 — Weekday. Today is Wednesday; what day is it in 45 days? 45 mod 7 = 3 → Wednesday + 3 = Saturday.

Example 2 — Even/odd and divisibility. mod 2 splits parity instantly; mod 9 gives the digit-sum test: 7,281 → 7+2+8+1 = 18 → divisible by 9. "Casting out nines" checks arithmetic: 47×53 = 2,491? 47≡2, 53≡8, product≡16≡7 (mod 9); 2,491 → 16 → 7 ✓.

Example 3 — RSA in one line. Encryption: c = mᵉ mod n; decryption: m = cᵈ mod n. The trapdoor is that factoring n = pq is hard — modular exponentiation is easy to do, impossible to undo without the factors.

Common mistakes and myths

Negative remainders — −7 mod 3: math convention gives 2 (remainder in [0, n)), but C/Java's % gives −1; know your language before hashing negatives.
Dividing in modular arithmetic — division needs the modular inverse, which exists only when gcd(a, n) = 1; "just divide" fails mod composites.
(a × b) mod n ≠ (a mod n) × (b mod n) forgetting the final reduce — the intermediate can overflow; reduce at every step in code.
Assuming mod distributes over exponents directly — use Fermat's little theorem: aᵖ⁻¹ ≡ 1 (mod p) for prime p, so exponents reduce mod (p−1).
Using mod for crypto without care — timing leaks and weak padding break naive implementations; use vetted libraries, never hand-rolled ciphers.

Frequently Asked Questions

What does "mod" mean?

a mod n is the remainder when a is divided by n: 17 mod 5 = 2 because 17 = 3×5 + 2. The result always lands in 0..n−1. Programmers write 17 % 5; mathematicians write 17 ≡ 2 (mod 5) — "17 is congruent to 2 modulo 5," meaning they differ by a multiple of 5. Everyday mod: clocks (mod 12/24), weekdays (mod 7), even-odd (mod 2).

How do the modular arithmetic rules work?

Mod distributes over +, −, ×: (a + b) mod n = ((a mod n) + (b mod n)) mod n. (97 × 84) mod 10 = (7 × 4) mod 10 = 8 — the last digit of any product depends only on last digits. This lets you shrink numbers BEFORE they explode — essential for programming (avoiding overflow) and for hand-checking arithmetic via mod 9 digit sums.

How does mod apply to clocks and calendars?

Time: 22:00 + 5 hours = 27 mod 24 = 3:00. Weekdays: 100 days from Tuesday = 100 mod 7 = 2 → Thursday. Months cycle mod 12; zodiac years mod 12; centuries mod 4/100/400 for leap years. Any repeating cycle is modular arithmetic wearing a costume — find the period, reduce the offset mod period, count from the anchor.

How do I compute huge powers with mod?

Powers mod n cycle. 3ⁿ mod 7: 3, 2, 6, 4, 5, 1, then repeats (period 6). So 3¹⁰⁰ mod 7: 100 mod 6 = 4 → same as 3⁴ mod 7 = 4. Faster method (binary exponentiation): square-and-multiply reduces mod at every step — computers do 3^(10⁹) mod 7 in ~30 multiplications. Fermat's little theorem guarantees the cycle: a^(p−1) ≡ 1 mod p for prime p.

Where is mod used in real systems?

Check digits: ISBN-10 verifies via mod 11; credit cards via Luhn (mod 10); Chinese ID numbers mod 11. Hashing: hash table slots = hash mod table_size. Crypto: RSA is modular exponentiation. Circular buffers wrap with mod. Even parity bits are mod 2 sums. Whenever a system needs to wrap, cycle, or verify — mod is underneath.

What mistakes happen with modular arithmetic?

(1) Negative mod: −7 mod 3 in math = 2 (−7 = −3×3 + 2), but C/Java % gives −1 — languages differ, normalize with ((a % n) + n) % n; (2) mod does NOT distribute over division — no (a/b) mod n without modular inverses; (3) forgetting the result range is 0..n−1, never n; (4) reducing the exponent mod n directly — exponents reduce mod (p−1) via Fermat, a subtle but classic exam trap; (5) assuming cycles have period n — 2ⁿ mod 7 has period 3, not 7.