Modular Arithmetic
Number Theory & Cryptographic Math
Chapter 3 · Modular Arithmetic
Chapter 2 built the division algorithm and treated the remainder r as a byproduct — something left over after the "real" answer, the quotient. Modular arithmetic flips that entirely: the remainder is the whole answer, and the quotient is thrown away. Everything from here to RSA itself is built on that single reframing.
Congruence: "Same Remainder" as an Equals Sign
Two integers a and b are congruent modulo n — written a ≡ b (mod n) — if they leave the same remainder when divided by n, which is exactly equivalent to saying n | (a − b).
42 mod 13 = 3 and 3 mod 13 = 3 — same remainder, so 42 ≡ 3 (mod 13). Confirming the alternate definition: 13 | (42 − 3), since 42 − 3 = 39 = 13 × 3.
Addition, Subtraction, and Multiplication All "Just Work"
The single most useful practical fact in this entire chapter: you can reduce modulo n at any point during a computation — before, during, or after — without ever changing the final answer modulo n.
(a + b) mod n = ((a mod n) + (b mod n)) mod n, and the identical shape holds for subtraction and multiplication. Numbers can be kept small throughout a calculation instead of letting them grow to their full, unreduced size.
a=987,654,321, b=123,456,789, modulus 1,000. Multiplying fully first, then reducing: (a×b) mod 1000 = 269. Reducing each operand first, then multiplying, then reducing again: ((a mod 1000)×(b mod 1000)) mod 1000 = 269 — identical. The same match holds for addition (110 both ways) and subtraction (532 both ways).
This is not a minor convenience — it's the entire reason modular exponentiation (Chapter 7) is computationally feasible at all for the enormous numbers RSA actually uses: intermediate values never need to grow beyond the modulus itself, no matter how large the final unreduced answer would otherwise be.
Division Doesn't Work the Same Simple Way
Addition, subtraction, and multiplication all reduce cleanly under a modulus. Division does not have an equally simple counterpart — there's no general rule like (a ÷ b) mod n = ((a mod n) ÷ (b mod n)) mod n, because ordinary division isn't guaranteed to produce a whole number, and modular arithmetic only deals in integers.
1/b would, but only exists under specific conditions. Chapter 5 builds this directly, and it's one of the two pieces (alongside Chapter 7's fast exponentiation) that make RSA's own decryption step work at all.
A Real Cross-Language Gotcha: What % Actually Does With Negative Numbers
Chapter 2 already flagged this once — now it matters directly. Programming languages genuinely disagree about what % returns for a negative operand:
| Language | -7 % 3 | Convention |
|---|---|---|
| Python | 2 | Floored — result always shares the divisor's sign (matches Chapter 2's division algorithm exactly) |
| JavaScript | -1 | Truncated toward zero — result shares the dividend's sign |
| Java | -1 | Truncated toward zero |
| C / C++ (C99 and later) | -1 | Truncated toward zero |
-7 % 3 gives 2. A simulated truncating-toward-zero remainder (the C/JavaScript/Java style) gives -1 for the exact same inputs — the two conventions genuinely disagree, not just in presentation but in the actual returned value.
-23: a truncating language's naive hash % table_size gives -3 — a genuinely invalid, negative array index, and a real out-of-bounds risk in a language that allows negative indexing to silently wrap or crash. The fix, verified directly, works regardless of which convention the language uses: ((a % n) + n) % n normalizes -23 down to 7, a valid bucket index every time.
Real Relevance: Clocks, Weekdays, and Wraparound
A 12-hour clock is arithmetic modulo 12; days of the week cycle modulo 7; a circular buffer's write position wraps modulo its own capacity. Any time a quantity needs to "wrap around" back to the start after reaching a fixed limit, that's modular arithmetic, whether or not the code ever calls it that.
Modular Arithmetic in Code
Hands-On Exercises
Determine whether 158 ≡ 38 (mod 12), using both the "same remainder" definition and the n | (a−b) definition. Show both checks agree.
Using this chapter's own reduce-anytime property, compute (456789 × 987654) mod 100 two ways: fully multiplying then reducing, and reducing each operand to its last two digits first, then multiplying, then reducing. Show both give the same result.
A hash produces the value -41 for some key, and the hash table has 8 buckets. Using this chapter's own normalization formula, compute the correct, valid bucket index — and explain, using this chapter's own truncating-vs-floored comparison, what a language using truncation toward zero would compute for -41 % 8 without normalization, and why that value is unusable as an index.
Chapter 3 Quick Reference
- Congruence:
a ≡ b (mod n)meansaandbshare the same remainder modn, equivalentlyn | (a−b) - Reduce-anytime property: addition, subtraction, and multiplication can all be reduced mod
nat any point without changing the final answer - Division has no equally simple rule — needs a modular inverse (Chapter 5)
- Cross-language gotcha: Python floors (result matches divisor's sign); JavaScript/Java/C truncate toward zero (result matches dividend's sign) — genuinely different values for the same negative input
- Universal fix:
((a % n) + n) % nalways returns a value in[0, n), regardless of language convention - Next chapter: The Euclidean algorithm and GCD