Modular Arithmetic in Contests — Math for Competitive Programming | Sabaoon Academy

Most competitive programming problems that involve large counts ask you to output the answer modulo 10⁹ + 7 (or similar). Mastering modular arithmetic is non-negotiable.

The Standard Modulus

MOD = 10**9 + 7 is a prime chosen because:

It fits in a 32-bit signed integer (just barely)
Products of two numbers mod p fit in a 64-bit integer (no overflow in most languages)
Being prime enables modular inverses for all non-zero values

MOD = 10**9 + 7

Basic Operations

# Addition
(a + b) % MOD

# Subtraction (add MOD to prevent negative)
(a - b + MOD) % MOD

# Multiplication
(a * b) % MOD

# Apply mod after every operation to keep numbers small
result = 1
for x in arr:
    result = result * x % MOD

Modular Exponentiation

pow(base, exp, mod) in Python is fast exponentiation — O(log exp). Use it everywhere:

pow(2, 10**18, MOD)   # instant

Manual implementation:

def power(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:               # if exp is odd
            result = result * base % mod
        base = base * base % mod  # square the base
        exp >>= 1                 # halve the exponent
    return result

Modular Inverse

The inverse of a (mod p) is a number x such that ax ≡ 1 (mod p).

By Fermat's little theorem (p prime, gcd(a,p)=1):

def mod_inv(a, p=MOD):
    return pow(a, p - 2, p)

By extended Euclidean algorithm (works for any modulus m where gcd(a,m)=1):

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inv_general(a, m):
    g, x, _ = extended_gcd(a % m, m)
    assert g == 1, "Inverse doesn't exist"
    return x % m

Precomputed Factorials and Inverse Factorials

For computing many combinations mod p, precompute all factorials and their inverses upfront:

def precompute(n, mod=MOD):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod

    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % mod

    return fact, inv_fact

MAXN = 10**6 + 5
fact, inv_fact = precompute(MAXN)

def comb(n, k, mod=MOD):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

def perm(n, k, mod=MOD):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[n-k] % mod

After O(N) precomputation, each comb(n, k) query is O(1).

Batch Modular Inverses

Computing n modular inverses individually costs O(n log p). This linear sieve method does all inverses 1..n in O(n):

def batch_inv(n, mod=MOD):
    inv = [0, 1]
    for i in range(2, n + 1):
        inv.append(-(mod // i) * inv[mod % i] % mod)
    return inv

Mathematical basis: inv[i] = -(mod // i) * inv[mod % i] % mod derived from i × ⌊mod/i⌋ + (mod % i) ≡ 0 (mod mod).

Lucas' Theorem

For computing C(n, k) mod p when n is very large (larger than can be precomputed):

Lucas' theorem: if p is prime:

C(n, k) mod p = C(n₀, k₀) × C(n₁, k₁) × ... (mod p)

where nᵢ, kᵢ are the digits of n, k in base p.

def lucas(n, k, p):
    if k == 0:
        return 1
    return comb(n % p, k % p) * lucas(n // p, k // p, p) % p

Use when n > 10⁶ but p is small (e.g., p = 10⁹+7 won't help; use for small prime p like 7 or 97).

Chinese Remainder Theorem (CRT)

Reconstruct a number from its remainders mod several coprime moduli.

Problem: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂). Find x mod (m₁m₂).

def crt2(a1, m1, a2, m2):
    # Find x = a1 + m1*t such that x ≡ a2 (mod m2)
    # m1*t ≡ (a2 - a1) (mod m2)
    diff = (a2 - a1) % m2
    t = diff * mod_inv_general(m1, m2) % m2
    x = a1 + m1 * t
    return x % (m1 * m2), m1 * m2

# Extend to multiple congruences
def crt(remainders, moduli):
    x, m = remainders[0], moduli[0]
    for ai, mi in zip(remainders[1:], moduli[1:]):
        x, m = crt2(x, m, ai, mi)
    return x, m

CRT appears in: problems with multiple constraints, hash collision avoidance using two primes (double hashing), reconstructing large numbers from parts.

Garner's Algorithm

When moduli are not coprime or you need to reconstruct the actual integer value (not just its remainder), use Garner's algorithm:

def garner(remainders, moduli, target_mod=MOD):
    # Mixed-radix representation
    # Result: coefficients c such that x = c₀ + c₁m₀ + c₂m₀m₁ + ...
    n = len(remainders)
    coeffs = list(remainders)
    prefix_mods = [1] * n

    for i in range(1, n):
        for j in range(i):
            # coeffs[i] = (coeffs[i] - coeffs[j]) * inv(prefix_mods[i]) mod moduli[i]
            coeffs[i] = (coeffs[i] - coeffs[j]) * mod_inv_general(prefix_mods[i], moduli[i]) % moduli[i]
        prefix_mods[i] = prefix_mods[i-1] * moduli[i-1] % target_mod

    result = 0
    for i in range(n):
        result = (result + coeffs[i] * prefix_mods[i]) % target_mod
    return result

Common Pitfalls

Negative results: always add MOD after subtraction.

# Wrong: (a - b) % MOD  — can be negative in some languages
# Right:
(a - b + MOD) % MOD

Overflow before mod: in Python this is never an issue (arbitrary precision). In C++/Java, always apply mod before multiplying if values could be close to 10⁹.

Division is not mod division: (a / b) % MOD ≠ (a % MOD) / (b % MOD). Use the modular inverse: a * mod_inv(b) % MOD.

Key Takeaways

MOD = 10**9 + 7 — standard prime modulus. Use pow(base, exp, MOD) for fast exponentiation.
Modular inverse by Fermat: pow(a, MOD-2, MOD). Works when MOD is prime and gcd(a, MOD) = 1.
Precompute factorials and inverse factorials in O(N) for O(1) combination queries.
Batch modular inverses for 1..n in O(n) using the linear recurrence.
Lucas' theorem: compute C(n,k) mod p for large n when p is small.
CRT: reconstruct a number from congruences modulo coprime moduli. Double hashing uses two primes to minimise collision probability.