2. Modular Arithmetic

Level: Beginner You'll use this for: hashing, hash tables, load balancing, checksums, and the entire foundation of cryptography (Ch. 24).

The idea

a mod n is the remainder when a is divided by n. Think of a clock: 14:00 mod 12 = 2:00. Numbers "wrap around" after reaching n.

>>> 17 % 5     # 2
>>> -1 % 5     # 4 in Python (always non-negative); -1 in C/Java (sign of dividend)

Careful: the sign convention for negative numbers differs across languages. Python and math convention give a non-negative result; C, Java, and JavaScript give a result with the sign of the dividend. This is a real source of off-by-one/wraparound bugs when porting code.

How to compute `a mod n` by hand

a mod n = a - n · ⌊a/n⌋ — divide, round the quotient down to the nearest whole number (floor), multiply that back by n, and subtract from a. Whatever's left is the remainder.

17 mod 5:
  17 ÷ 5 = 3.4  ->  floor to 3     (5 fits into 17 three whole times)
  3 × 5 = 15
  17 - 15 = 2                       -> 17 mod 5 = 2   ✓ matches the code above

-1 mod 5 (Python/math convention):
  -1 ÷ 5 = -0.2  ->  floor to -1    (floor rounds toward negative infinity,
                                      not toward zero — this is the crux of
                                      the sign difference vs. C/Java)
  -1 × 5 = -5
  -1 - (-5) = 4                     -> -1 mod 5 = 4    ✓ matches the code above

C-family languages instead truncate toward zero (-1 ÷ 5 = -0.2 -> 0, giving -1 - 0 = -1), which is exactly why the same expression produces a different sign in Python vs. C — the division step rounds differently, not the subtraction.

Congruence

a ≡ b (mod n) means a and b have the same remainder mod n. This is the backbone of clock arithmetic, cyclic buffers, and (later) RSA.

Worked example: round-robin load balancing

You have 5 backend servers (indices 0–4) and need to route request #i to server i mod 5.

servers = ["srv0", "srv1", "srv2", "srv3", "srv4"]
for request_id in [0, 1, 5, 6, 12]:
    print(request_id, "->", servers[request_id % 5])
# 0 -> srv0, 1 -> srv1, 5 -> srv0, 6 -> srv1, 12 -> srv2

Worked example: hash table bucket index

A hash table with n buckets computes bucket = hash(key) % n. This is why hash table sizes are often chosen as powers of 2 — x % 2^k is just x & (2^k - 1), a single fast bitwise AND instead of a division.

n = 16               # 2^4 buckets
key_hash = 0b101101010111  # some hash value
bucket_via_mod = key_hash % n
bucket_via_mask = key_hash & (n - 1)
assert bucket_via_mod == bucket_via_mask

Real-life engineering ties

SWE: circular buffers, ring indices (idx = (idx + 1) % capacity), date/time math (day-of-week = days_since_epoch % 7).
Network: TCP sequence numbers wrap at 2³² and are compared using modular ("serial number") arithmetic, not plain </> (RFC 1982) — otherwise wraparound would make a new packet look "older" than an old one.
Security: every symmetric/asymmetric cipher, hash function, and CRC checksum operates in modular arithmetic. Consistent hashing (used to shard data across nodes with minimal reshuffling when nodes are added) is modular arithmetic on a "hash ring."

More real-life examples:

Distributed databases and caches (DynamoDB, Cassandra, memcached) use consistent hashing to shard keys across nodes with minimal data movement when nodes are added or removed.
Credit card numbers, ISBNs, and IMEI numbers all carry a check digit computed with modular arithmetic (the Luhn algorithm) so a single mistyped digit is caught before the number is even looked up.
Ethernet frames, ZIP files, and PNG images all carry a CRC32 checksum — a value computed over the data modulo a fixed generator polynomial — to catch accidental corruption in transit.
Round-robin DNS and round-robin CPU scheduling both assign the next resource using index mod n, the same operation as the load-balancer example above.

Common mistake

Forgetting that % in most C-family languages can return negative results, breaking array-index code that assumes 0 <= result < n. Fix: ((a % n) + n) % n.