Modular Arithmetic
Modular arithmetic is the system of arithmetic where numbers wrap around after reaching a fixed modulus m. It is the mathematics of clocks, hash tables, cy...
The Mechanics of Modular Arithmetic and Why It Is Ubiquitous
Modular arithmetic is the system of arithmetic where numbers wrap around after reaching a fixed modulus m. It is the mathematics of clocks, hash tables, cyclic structures, and cryptography. In competitive programming, intermediate results in combinatorics or number theory problems frequently exceed 64-bit integer limits, making it necessary to work modulo a large prime — typically 10^9 + 7 or 10^9 + 9, both of which are prime and fit comfortably in a 32-bit integer after a modular reduction.
The three fundamental properties that make modular arithmetic tractable are: (a + b) mod m = ((a mod m) + (b mod m)) mod m; (a * b) mod m = ((a mod m) * (b mod m)) mod m; and (a - b) mod m = ((a mod m) - (b mod m) + m) mod m. The addition of m before taking mod in the subtraction case prevents negative results in languages where the modulo of a negative number is implementation-defined. Division does not distribute over mod directly — you must multiply by the modular inverse instead.
Fast modular exponentiation (also called binary exponentiation or exponentiation by squaring) computes a^b mod m in O(log b) time. The algorithm repeatedly squares the base and multiplies into the result when the corresponding bit of b is set: result = 1; while b > 0: if b & 1: result = result * a % m; a = a * a % m; b >>= 1. This is one of the most frequently implemented subroutines in competitive programming.
Modular Inverse and Its Role in Combinatorial Computations
Division inside a modular context requires the modular inverse. If you want to compute (a / b) mod m, you instead compute (a * b^(-1)) mod m. When m is prime and b is not divisible by m, Fermat's little theorem guarantees b^(m-1) ≡ 1 (mod m), so b^(-1) ≡ b^(m-2) (mod m). This lets you compute modular inverses in O(log m) time using fast exponentiation.
A common optimization is precomputing inverse factorials for all numbers up to N when you need to answer many combinatorial queries. First compute fact[i] = i! mod m for i from 0 to N. Then compute inv_fact[N] = fast_pow(fact[N], m-2, m), and fill inv_fact[i] = inv_fact[i+1] * (i+1) % m from N-1 down to 0. This O(N) precomputation allows O(1) evaluation of C(n, k) = fact[n] * inv_fact[k] * inv_fact[n-k] % m.
Another approach computes modular inverses for all numbers from 1 to N in O(N) time using the recurrence inv[i] = -(m / i) * inv[m % i] % m, initialized with inv[1] = 1. This linear sieve of modular inverses is useful when N is large and you cannot afford O(N log m) precomputation. Understanding both the Fermat method and the linear recurrence method gives you flexibility depending on problem constraints.
Overflow Management and Practical Implementation Pitfalls
The most common bug in modular arithmetic code is integer overflow. In C++, multiplying two 32-bit integers that are each close to 10^9 produces a result close to 10^18, which fits in a 64-bit long long but not in a 32-bit int. Always perform the multiplication in 64-bit space before taking mod: result = (long long)a * b % m. In Python, integers have arbitrary precision so overflow is never an issue, but explicit mod operations are still necessary to keep numbers small.
A subtler pitfall is taking mod too infrequently. After several additions or multiplications without intermediate reduction, even a 64-bit integer can overflow. The safe practice is to reduce modulo m after every arithmetic operation. This is especially important in matrix exponentiation, where matrix entries accumulate from many multiplications and can grow very large if you forget to reduce.
Modular arithmetic also appears in hashing, where polynomial rolling hash computes hash(s) = s[0] * p^(n-1) + s[1] * p^(n-2) + ... + s[n-1] all modulo some large m. To minimize collision probability, use two different moduli simultaneously (double hashing). A concrete tip: choose p to be a prime larger than the character set size (e.g., 31 for lowercase English letters) and m to be a large prime like 10^9 + 7. Precompute prefix hashes and powers of p to answer substring hash queries in O(1) after O(n) preprocessing.