Fermat's Little Theorem

I was grinding 1622. Fancy Sequence — a hard daily problem that needed modular inverse to compute 3^-1 % MOD. At first I thought — just divide, right? Turns out division doesn't work under modulo. That's when I discovered Fermat's Little Theorem, and it completely changed how I think about modular arithmetic.

The Problem With Division Under Mod

Say you want (9 / 3) % 7. Your instinct is:

(9 // 3) % 7 == 3  # this works here
(9 % 7) // (3 % 7) == 2 // 3  # wrong — not even an integer

Division doesn't distribute over modulo the way addition or multiplication does. So C(n, r) % MOD can't be computed by naively dividing factorials. You need the modular inverse.

The Theorem

Fermat's Little Theorem states: if p is prime and a is not divisible by p, then:

a^(p-1) ≡ 1 (mod p)

Multiply both sides by a^(-1):

a^(p-2) ≡ a^(-1) (mod p)

So instead of dividing by a, you multiply by a^(p-2) % p. That's your modular inverse.

For 3^-1 % 7:

p = 7, a = 3
3^(7-2) % 7 = 3^5 % 7 = 243 % 7 = 5

Check: 3 * 5 = 15, and 15 % 7 = 1. Correct — 5 is the inverse of 3 mod 7.

Fast Exponentiation

Computing a^(p-2) % p directly would be slow — p can be 10^9 + 7. You need binary exponentiation (fast power), which does it in O(log p).

The idea: instead of multiplying a by itself p-2 times, square repeatedly:

a^13 = a^8 * a^4 * a^1   (because 13 = 1101 in binary)

Each step you either square or square-and-multiply based on the current bit. That's O(log p) multiplications instead of O(p).

def fast_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:          # current bit is 1 — multiply in
            result = result * base % mod
        base = base * base % mod  # square
        exp //= 2                 # shift right
    return result

# 3^-1 mod (10^9+7)
print(fast_pow(3, 10**9 + 5, 10**9 + 7))  # = 333333336

Python's built-in pow(a, b, mod) does exactly this — three-argument pow is already optimized fast exponentiation.

pow(3, 10**9 + 5, 10**9 + 7)  # same result, cleaner

Applying It to nCr

The problem didn't need nCr directly — but once you understand modular inverse, this is the most common place you'll use it. Anytime you see C(n, r) % MOD in a problem, this is the pattern.

Now we can compute C(n, r) % p cleanly:

C(n, r) = n! / (r! * (n-r)!)
        = n! * inv(r!) * inv((n-r)!) mod p

MOD = 10**9 + 7

def modinv(a):
    return pow(a, MOD - 2, MOD)

def ncr(n, r):
    if r > n: return 0
    num = 1
    den = 1
    for i in range(r):
        num = num * (n - i) % MOD
        den = den * (i + 1) % MOD
    return num * modinv(den) % MOD

For multiple queries, precompute all factorials upfront:

MOD = 10**9 + 7
MAXN = 10**6 + 1

fact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i-1] * i % MOD

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

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

O(n) precomputation, O(1) per query after that.

When Can You Use It?

Condition	Fermat's works?
`p` is prime	Yes
`p = 10^9 + 7` (most LC problems)	Yes — it's prime
`p` is not prime	No — use extended Euclidean
`a` is divisible by `p`	No — inverse doesn't exist

The reason LeetCode always uses 10^9 + 7 as the modulus isn't arbitrary — it's a large prime, which makes Fermat's theorem applicable.

Fermat's Little Theorem — the math behind modular inverse