Modular Arithmetic
The problem
Many systems need values that wrap around (ring buffers, clock hours) or that must be spread evenly across a fixed number of buckets (hash tables). Modular arithmetic is the algebra of remainders — it gives wraparound and bucketing a principled, composable definition instead of ad hoc rules.
Why now
Number systems and bases gives positional representation, but not the algebra of what happens when a count exceeds its representation's range. Without modular arithmetic, 'hash this key into one of N buckets' has no formal definition — you'd be inventing a rule instead of applying one with known, provable properties like (a+b) mod n = ((a mod n)+(b mod n)) mod n.
Mental model
Modular arithmetic is clock arithmetic — once you reach the modulus you wrap back to zero. '17 mod 5' asks 'how far past the last full wrap am I?' Once hashing, cyclic buffers, and calendar math are all seen as this one wraparound idea, each stops being a special case you memorize separately.
Requires
- Number Systems & BasesMathematical Thinking
Modular arithmetic operates on integers represented positionally, and the wraparound intuition builds directly on the base/remainder relationship introduced there.
Helps
- Functions & RelationsMathematical Thinking
mod n is itself a function from the integers to {0, …, n-1}; seeing it as a function clarifies why it is well-defined and how it composes with other operations.
Unlocks
Related
Used in
- Hash table bucket indexing (hash(key) mod n)
- Circular buffers and ring queues
- Consistent hashing in distributed caches (e.g. Memcached, DynamoDB)
- Cron schedules and calendar wraparound
- Modular exponentiation in RSA and other cryptographic algorithms
Projects
- Implement a fixed-size circular buffer using only modular arithmetic for index wraparound
- Implement a simple hash table and measure bucket-fill distribution as you vary the modulus
Examples
- A ring buffer of size 8: writing at index 7 then advancing goes to index 0, i.e. (7+1) mod 8
- Consistent hashing places servers and keys on a mod-n ring so only a fraction of keys remap when a server is added
Resources
Mastery checklist
- I can compute a mod b by hand for positive and negative a
- I can explain why (a+b) mod n = ((a mod n)+(b mod n)) mod n and use it to simplify a calculation
- I can implement wraparound indexing for a ring buffer without an if-statement
- I can explain why consistent hashing needs modular arithmetic on a ring rather than a plain mod n