Algorithms / Modular Arithmetic Interview
Least You Need to Know: Modular Arithmetic Patterns, Inverses, and Residue Reasoning
Interview modular arithmetic is about replacing large values by equivalent residues without breaking the operation you care about. The key checkpoints are congruence rules, negative residues, and knowing when division is legal through inverses.
The least you need to know
- If `a ≡ b (mod m)`, then you may add, subtract, and multiply on both sides modulo `m`.
- Division modulo `m` is really multiplication by an inverse, so it only works when that inverse exists.
- A number `a` has an inverse modulo `m` exactly when `gcd(a, m) = 1`.
- Negative numbers can be replaced by equivalent nonnegative residues such as `-1 ≡ m-1 (mod m)`.
- Reduce early and often to keep intermediate values small while preserving correctness.
Key notation
a ≡ b (mod m)
`m` divides `a - b`
a^{-1} mod m
value with `a * a^{-1} ≡ 1 (mod m)` when it exists
[a]_m
the residue class of `a` modulo `m`
Tiny worked example
- Suppose you need `(10^9 + 9)^2 mod 7`.
- First reduce `10^9 + 9` modulo `7`.
- Once you replace the large value by its residue, squaring the residue gives the same final answer modulo `7`.
Common mistakes
- Students often cancel factors modulo `m` without checking that the factor is invertible.
- A negative remainder is not wrong, but mixing sign conventions mid-solution causes errors.
- Congruence preserves the operation only when you use a rule that is actually valid.
How to recognize this kind of problem
- The prompt asks for only the remainder, parity class, wraparound index, or hashing bucket.
- Numbers are too large to expand directly, so reducing modulo a base is the natural simplification.
- The solution depends on recognizing that division means inverse, not ordinary real-number division.