Modular Arithmetic — ModExp, ModInverse, Fermat's Little Theorem

Every competitive programming problem involving large numbers ends with 'output the answer modulo 10^9+7'. Every RSA operation involves modular exponentiation. Every Diffie-Hellman key exchange involves modular arithmetic. Understanding modular arithmetic is not optional for systems engineers or competitive programmers — it is the foundation layer that makes everything else possible.

The key insight that unlocks modular arithmetic: (a × b) mod m = ((a mod m) × (b mod m)) mod m. This distributivity means you can reduce intermediate values at every step, keeping numbers in range, without affecting the final result. Without this, even simple operations on 'big' numbers would overflow. With it, you can compute 2^(10^18) mod (10^9+7) with Python's built-in pow(2, 1018, 109+7) — under a microsecond.

Modular Arithmetic Properties

The key property: modular operations distribute over addition, subtraction, and multiplication: (a + b) mod m = ((a mod m) + (b mod m)) mod m (a × b) mod m = ((a mod m) × (b mod m)) mod m (a - b) mod m = ((a mod m) - (b mod m) + m) mod m

Division requires modular inverse — you cannot simply divide.

Fast Modular Exponentiation

Compute a^b mod m in O(log b) using repeated squaring. Essential for cryptography and competitive programming.

def mod_exp(base: int, exp: int, mod: int) -> int:
    """Compute base^exp mod m in O(log exp)."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:  # if exp is odd
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

print(mod_exp(2, 10, 1000))   # 1024 mod 1000 = 24
print(mod_exp(3, 200, 13))    # 3^200 mod 13 = 9
print(mod_exp(2, 10**18, 10**9+7))  # handles huge exponents
# Python built-in: pow(base, exp, mod)
print(pow(2, 10, 1000))  # 24 — uses same algorithm

Modular Inverse — Fermat's Little Theorem

The modular inverse of a mod m is x such that a*x ≡ 1 (mod m). When m is prime, Fermat's Little Theorem gives: a^(m-1) ≡ 1 (mod m), so a^(-1) ≡ a^(m-2) (mod m). Compute in O(log m).

MOD = 10**9 + 7  # common prime modulus in competitive programming

def mod_inv_fermat(a: int, mod: int = MOD) -> int:
    """Modular inverse using Fermat's little theorem.
    Only works when mod is prime."""
    return pow(a, mod - 2, mod)

print(mod_inv_fermat(3))    # 333333336 (3 * 333333336 mod MOD = 1)
print(3 * mod_inv_fermat(3) % MOD)  # 1 ✓

# Modular division: a/b mod m = a * inv(b) mod m
def mod_div(a: int, b: int, mod: int = MOD) -> int:
    return a * mod_inv_fermat(b, mod) % mod

print(mod_div(10, 2))  # 5 (10/2 mod MOD = 5)
print(mod_div(7, 3))   # (7 * inv(3)) mod MOD

Precomputing Factorials and Inverse Factorials

For combinatorics problems (nCr mod p), precompute factorial and inverse factorial arrays.

MOD = 10**9 + 7

def precompute_factorials(n: int, mod: int = 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

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

fact, inv_fact = precompute_factorials(10**6)
print(n_choose_r(10, 3, fact, inv_fact))   # 120
print(n_choose_r(20, 10, fact, inv_fact))  # 184756

Wilson's Theorem and Fermat's Little Theorem

Fermat's Little Theorem: If p is prime and gcd(a,p)=1, then a^(p-1) ≡ 1 (mod p).

Wilson's Theorem: p is prime iff (p-1)! ≡ -1 (mod p). Theoretically elegant but computationally impractical for primality testing.

Euler's Theorem (generalisation): a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1. Fermat's is the special case when n is prime (φ(p)=p-1).

Frequently Asked Questions