Modular Arithmetic
Modular arithmetic is arithmetic performed within a fixed range [0, m-1] where numbers "wrap around" after reaching m. It is the engine behind competitive programming: the answer modulo 10^9+7 appears in hundreds of problems because results would otherwise overflow any data type. Understanding it deeply unlocks problems in combinatorics, cryptography, and number theory.
Why Modulo in Competitive Programming?
Combinatorial results (nCr, Catalan numbers, path counts) grow astronomically fast
JavaScript safe integer limit is 2^53 ≈ 9×10^15 — easily exceeded by products
10^9+7 is prime, which guarantees modular inverses exist for all non-zero values
10^9+7 fits in a 32-bit signed integer, so (a*b) % MOD fits in 64-bit
Basic Rules
Operation | Formula | Note |
|---|---|---|
Addition | (a + b) % m | Always safe — no overflow before mod |
Subtraction | ((a - b) % m + m) % m | Add m to handle negative results |
Multiplication | (a % m) * (b % m) % m | Reduce both operands first |
Division | a * modInverse(b, m) % m | Only when gcd(b, m) = 1 |
const MOD = 1_000_000_007n; // 10^9 + 7 as BigInt for safety
function addMod(a: bigint, b: bigint): bigint {
return (a + b) % MOD;
}
function subMod(a: bigint, b: bigint): bigint {
return ((a - b) % MOD + MOD) % MOD; // +MOD prevents negative result
}
function mulMod(a: bigint, b: bigint): bigint {
return (a * b) % MOD;
}
// Example: (10^9 + 6) + (10^9 + 6) mod (10^9+7)
const x = 1_000_000_006n;
console.log(addMod(x, x)); // 1000000005n (wraps around correctly)Modular Exponentiation — O(log n)
Computing a^b mod m naively multiplies b times. Binary (fast) exponentiation squares the base and
halves the exponent at each step — O(log b) multiplications. This is the workhorse of modular arithmetic.
// Modular fast power — BigInt version
function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
let result = 1n;
base = base % mod;
while (exp > 0n) {
if (exp & 1n) result = result * base % mod; // if current bit is set
base = base * base % mod; // square the base
exp >>= 1n; // shift to next bit
}
return result;
}
const MOD = 1_000_000_007n;
// 2^10 mod 10^9+7 = 1024
console.log(modPow(2n, 10n, MOD)); // 1024n
// Very large exponent: 2^1000000000 mod 10^9+7
console.log(modPow(2n, 1_000_000_000n, MOD)); // 140625001n (computed in ~30 steps)Modular Inverse — Fermat's Little Theorem
The modular inverse of a modulo m is x such that a·x ≡ 1 (mod m). When m is prime and a is not divisible by m, Fermat's Little Theorem gives a clean formula:
a^(m-1) ≡ 1 (mod m) → a^(m-2) ≡ a^(-1) (mod m)
This means the inverse is just modPow(a, m-2, m).
function modInverse(a: bigint, mod: bigint): bigint {
// Works when mod is prime (Fermat's little theorem)
return modPow(a, mod - 2n, mod);
}
const MOD = 1_000_000_007n;
// Division by 3 mod 10^9+7: multiply by inverse of 3
const inv3 = modInverse(3n, MOD);
console.log(inv3); // 333333336n
console.log((3n * inv3) % MOD); // 1n ✓
// Safe modular division: a / b mod m = a * inv(b) mod m
function divMod(a: bigint, b: bigint, mod: bigint): bigint {
return a * modInverse(b, mod) % mod;
}
console.log(divMod(9n, 3n, MOD)); // 3n ✓Precomputing Factorials and Inverses
Combinatorics problems require computing nCr mod p for many values of n and r. Precomputing factorials and their inverses up to the maximum needed n brings each nCr query to O(1).
const MOD = 1_000_000_007n;
const MAXN = 1_000_001;
const fact = new Array<bigint>(MAXN);
const invFact = new Array<bigint>(MAXN);
function precompute() {
fact[0] = 1n;
for (let i = 1; i < MAXN; i++) {
fact[i] = fact[i - 1] * BigInt(i) % MOD;
}
invFact[MAXN - 1] = modPow(fact[MAXN - 1], MOD - 2n, MOD);
for (let i = MAXN - 2; i >= 0; i--) {
invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;
}
}
// nCr mod prime — O(1) per query after precompute()
function nCr(n: number, r: number): bigint {
if (r < 0 || r > n) return 0n;
return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
precompute();
console.log(nCr(10, 3)); // 120n
console.log(nCr(20, 10)); // 184756nLarge Fibonacci Modulo
Fibonacci numbers grow exponentially. Computing Fib(10^18) requires matrix exponentiation — raise a 2×2 matrix to the power n in O(log n) steps using the same binary exponentiation idea.
// Matrix multiply mod m
function matMul(A: bigint[][], B: bigint[][], mod: bigint): bigint[][] {
const n = A.length;
const C: bigint[][] = Array.from({ length: n }, () => new Array(n).fill(0n));
for (let i = 0; i < n; i++)
for (let k = 0; k < n; k++)
for (let j = 0; j < n; j++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
return C;
}
// Matrix fast power
function matPow(M: bigint[][], exp: bigint, mod: bigint): bigint[][] {
let result: bigint[][] = [[1n, 0n], [0n, 1n]]; // identity
while (exp > 0n) {
if (exp & 1n) result = matMul(result, M, mod);
M = matMul(M, M, mod);
exp >>= 1n;
}
return result;
}
// Fib(n) mod m using [[1,1],[1,0]]^n
function fibMod(n: number, mod: bigint): bigint {
if (n <= 1) return BigInt(n);
const M: bigint[][] = [[1n, 1n], [1n, 0n]];
return matPow(M, BigInt(n), mod)[0][1];
}
const MOD = 1_000_000_007n;
console.log(fibMod(10, MOD)); // 55n
console.log(fibMod(1_000_000, MOD)); // 209952n (computed in ~20 matrix multiplications)Quick Reference
Problem pattern | Tool to use |
|---|---|
Large sum or count modulo prime | (a+b)%MOD throughout |
Large product modulo prime | mulMod with BigInt, or modPow for powers |
Division modulo prime | Multiply by modular inverse (Fermat) |
nCr mod prime — many queries | Precompute factorial + inverse factorial tables |
a^b mod m — b is huge | modPow binary exponentiation O(log b) |
Fibonacci/sequence at index 10^18 | Matrix exponentiation O(k^3 log n) |