Modular Inverse via Fermat's Little Theorem

Pillar: Fix — "Fix the equation \(a \cdot x \equiv 1 \pmod{p}\). Fermat's theorem tells us \(x = a^{p-2} \bmod p\)."

---

The Setup

You need to compute \(\binom{n}{k} \bmod (10^9 + 7)\). That's \(\frac{n!}{k!(n-k)!}\). You know how to multiply under mod. You know how to exponentiate under mod. But there's a division sitting right there — \(n!\) divided by \(k!(n-k)!\) — and division doesn't work under mod.

Recall from Ch4 L1: \((6 \bmod 5) / (2 \bmod 5) = 1 / 2\), which is meaningless. You can't divide remainders and expect a correct answer.

So the question becomes: how do you "divide" in a world where only multiplication exists? You multiply by the inverse.

---

What Is a Modular Inverse?

In regular arithmetic, dividing by \(3\) is the same as multiplying by \(\frac{1}{3}\). The number \(\frac{1}{3}\) is the multiplicative inverse of \(3\) because \(3 \times \frac{1}{3} = 1\).

Modular arithmetic has the same idea, but the inverse is an integer.

The modular inverse of \(a\) modulo \(m\) is an integer \(a^{-1}\) such that:

\[a \cdot a^{-1} \equiv 1 \pmod{m}\]

Concrete example. What's \(3^{-1} \bmod 7\)? You need an integer \(x\) where \(3x \equiv 1 \pmod{7}\). Try values: \(3 \times 1 = 3\), \(3 \times 2 = 6\), \(3 \times 3 = 9 \equiv 2\), \(3 \times 4 = 12 \equiv 5\), \(3 \times 5 = 15 \equiv 1\). Found it: \(3^{-1} \equiv 5 \pmod{7}\).

Once you have the inverse, division becomes multiplication: \(a / b \bmod m = a \times b^{-1} \bmod m\).

---

When Does an Inverse Exist?

Not every number has an inverse. Consider \(4^{-1} \bmod 6\). You need \(4x \equiv 1 \pmod{6}\). Check every value in \(\{0, 1, 2, 3, 4, 5\}\): \(4 \times 0 = 0\), \(4 \times 1 = 4\), \(4 \times 2 = 8 \equiv 2\), \(4 \times 3 = 12 \equiv 0\), \(4 \times 4 = 16 \equiv 4\), \(4 \times 5 = 20 \equiv 2\). The results cycle through \(\{0, 4, 2, 0, 4, 2\}\) — the value \(1\) never appears. No inverse.

The pattern: \(4\) and \(6\) share a common factor of \(2\). Since \(4x\) is always even, \(4x - 1\) is always odd, so \(6\) can never divide \(4x - 1\).

Theorem. \(a\) has a modular inverse modulo \(m\) if and only if \(\gcd(a, m) = 1\).

The proof comes from Bezout's identity (Ch3 L3). If \(\gcd(a, m) = 1\), there exist integers \(x, y\) such that \(ax + my = 1\). Reducing both sides mod \(m\): \(ax \equiv 1 \pmod{m}\). That \(x\) is the inverse.

The critical consequence: when \(m\) is prime, every nonzero value has an inverse. If \(p\) is prime and \(1 \leq a < p\), then \(\gcd(a, p) = 1\) automatically. This is why competitive programming uses prime moduli.

---

Fermat's Little Theorem

Brute-forcing the inverse by trying all values from \(1\) to \(m-1\) is \(O(m)\) — far too slow when \(m = 10^9 + 7\). Fermat's Little Theorem gives us a direct formula.

Start with the example that makes the theorem obvious. Take \(p = 7\) and compute \(a^6 \bmod 7\) for every nonzero \(a\):

\(a\)	\(a^2\)	\(a^3\)	\(a^4\)	\(a^5\)	\(a^6\)	\(a^6 \bmod 7\)
1	1	1	1	1	1	1
2	4	8	16	32	64	1
3	9	27	81	243	729	1
4	16	64	256	1024	4096	1
5	25	125	625	3125	15625	1
6	36	216	1296	7776	46656	1

Every row ends with \(1\). Every nonzero element raised to the \((p-1)\)-th power gives \(1\) modulo \(p\).

Fermat's Little Theorem. If \(p\) is prime and \(p \nmid a\), then:

\[a^{p-1} \equiv 1 \pmod{p}\]

Is this true for EVERY modulus, or only primes?

Only primes. Try \(a = 2\), \(m = 9\): \(2^8 = 256\), and \(256 \bmod 9 = 4 \neq 1\). The GCD is \(1\), but \(9\) is composite, and the theorem fails. For composite \(m\), you need Euler's Totient Theorem: \(a^{\phi(m)} \equiv 1 \pmod{m}\), where \(\phi(m)\) counts integers from \(1\) to \(m\) that are coprime to \(m\). When \(m\) is prime, \(\phi(m) = m - 1\), and you recover Fermat's theorem. The generalization is covered in Ch4 L5.

What about Carmichael numbers — composites that 'fake' being prime?

There exist rare composite numbers (like \(561 = 3 \times 11 \times 17\)) where \(a^{m-1} \equiv 1 \pmod{m}\) holds for all \(a\) coprime to \(m\). These are called Carmichael numbers, and they pass the Fermat test. The explanation comes from CRT: if \(m = p_1 \cdot p_2 \cdot p_3\) and \((p_i - 1) \mid (m - 1)\) for each prime factor, then Fermat's theorem works modulo each \(p_i\), and CRT glues the results together. This is why Fermat-based primality tests can be fooled, and why Miller-Rabin (Ch9 L5) is needed for reliable primality testing.

Now divide both sides by \(a\):

\[a^{p-2} \equiv a^{-1} \pmod{p}\]

That's the formula. The modular inverse of \(a\) modulo a prime \(p\) is \(a^{p-2} \bmod p\). Compute it with binary exponentiation from Ch4 L2: \(O(\log p)\) time.

---

The Critical Constraint

This method only works when the modulus is prime. If \(m\) is composite, \(a^{m-2} \bmod m\) is not the inverse of \(a\). Not even close.

Quick counterexample. Try \(m = 6\), \(a = 5\). Fermat's formula would give \(5^{6-2} = 5^4 = 625\). And \(625 \bmod 6 = 1\). But that's a coincidence. Try \(a = 2\): \(2^4 = 16\), \(16 \bmod 6 = 4\). Check: \(2 \times 4 = 8 \equiv 2 \pmod{6}\). Not \(1\). Wrong.

For composite moduli, you need the Extended Euclidean Algorithm (Ch4 L4). For the standard competitive programming modulus \(10^9 + 7\), Fermat's method is exactly right.

---

Worked Example

Compute \(3^{-1} \bmod 7\) using Fermat's Little Theorem.

Step 1. Confirm \(7\) is prime. It is.

Step 2. Apply the formula: \(3^{-1} \equiv 3^{7-2} \equiv 3^5 \pmod{7}\).

Step 3. Compute \(3^5\) using binary exponentiation. Write \(5\) in binary: \(5 = 101_2\).

Bit (right to left)	Action	base	result
Start	—	3	1
Bit 0 = 1	Multiply result by base, then square base	3	\(1 \times 3 = 3\)
—	Square base	\(3^2 \bmod 7 = 2\)	3
Bit 1 = 0	Skip multiply, square base	\(2^2 \bmod 7 = 4\)	3
Bit 2 = 1	Multiply result by base	4	\(3 \times 4 \bmod 7 = 5\)

Result: \(3^5 \bmod 7 = 5\).

Step 4. Verify: \(3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 \pmod{7}\). Correct.

---

Division Under Mod

With the inverse in hand, modular division becomes modular multiplication:

\[\frac{a}{b} \bmod p = a \times b^{-1} \bmod p = a \times b^{p-2} \bmod p\]

Trace it. Compute \(6 / 3 \bmod 7\).

• \(b^{-1} = 3^{-1} \bmod 7 = 5\) (computed above).
• \(a \times b^{-1} = 6 \times 5 = 30\).
• \(30 \bmod 7 = 2\).
• Sanity check: \(6 / 3 = 2\). Correct.

A less obvious example. Compute \(1 / 2 \bmod 7\).

• \(2^{-1} \equiv 2^5 \bmod 7 = 32 \bmod 7 = 4\).
• \(1 \times 4 = 4\).
• Verify: \(2 \times 4 = 8 \equiv 1 \pmod{7}\). Correct.

"Half" of \(1\) in mod \(7\) world is \(4\). Modular arithmetic doesn't care that \(1/2\) isn't an integer in the real numbers — it only cares that \(2 \times 4 \equiv 1\).

---

When the Inverse Doesn't Exist

If \(a \equiv 0 \pmod{p}\), then \(a\) is a multiple of \(p\), and \(\gcd(a, p) = p \neq 1\). No inverse exists. This is the modular equivalent of division by zero.

In code, calling modInverse(0, prime) computes \(0^{p-2} \bmod p = 0\), which silently gives a wrong answer — no exception, no crash, just a bad result. Guard against it.

For any nonzero \(a\) with a prime modulus, the inverse always exists. That's the guarantee Fermat gives you.

---

The Code

Modular Inverse

Using the modPow function from Ch4 L2:

long long modPow(long long base, long long exponent, long long mod) {
    long long result = 1;
    base %= mod;
    while (exponent > 0) {
        if (exponent & 1) result = result * base % mod;
        base = base * base % mod;
        exponent >>= 1;
    }
    return result;
}

long long modInverse(long long value, long long prime) {
    return modPow(value, prime - 2, prime);
}

\(O(\log p)\) time, \(O(1)\) space.

The entire computation reduces to one call to binary exponentiation. The exponent is \(p - 2\), which for \(p = 10^9 + 7\) means about \(30\) iterations of the squaring loop.

Modular Division

long long modDivide(long long numerator, long long denominator, long long prime) {
    return numerator % prime * modInverse(denominator, prime) % prime;
}

\(O(\log p)\) time, \(O(1)\) space.

Reduce the numerator first, multiply by the inverse, reduce again. The numerator % prime at the start handles the case where numerator hasn't been reduced yet.

---

Application: Combinatorics Under Mod

The payoff. To compute \(\binom{n}{k} \bmod p\), precompute factorials and their inverses:

const int MAXIMUM = 200001;
const long long MOD = 1000000007;
long long factorial[MAXIMUM], inverseFactorial[MAXIMUM];

void precomputeFactorials() {
    factorial[0] = 1;
    for (int i = 1; i < MAXIMUM; i++)
        factorial[i] = factorial[i - 1] * i % MOD;
    inverseFactorial[MAXIMUM - 1] = modInverse(factorial[MAXIMUM - 1], MOD);
    for (int i = MAXIMUM - 2; i >= 0; i--)
        inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % MOD;
}

long long choose(int totalItems, int chosenItems) {
    if (chosenItems < 0 || chosenItems > totalItems) return 0;
    return factorial[totalItems] % MOD
        * inverseFactorial[chosenItems] % MOD
        * inverseFactorial[totalItems - chosenItems] % MOD;
}

The trick in precomputeFactorials: you only call modInverse once (for the largest factorial), then derive all smaller inverse factorials by multiplying backwards. Since \((i!)^{-1} \times (i+1) = ((i+1)!)^{-1} \times (i+1)^2\)... actually, the cleaner way to see it: \(((i)!)^{-1} = ((i+1)!)^{-1} \times (i+1)\), because \((i+1)! = (i!) \times (i+1)\), so inverting both sides gives the recurrence. One modInverse call plus \(O(n)\) multiplications, instead of \(O(n \log p)\) for calling modInverse on every factorial.

This pattern — precomputed factorials and inverse factorials — appears in nearly every combinatorics problem on Codeforces and LeetCode.

---

Common Mistakes

• Using Fermat's formula with a composite modulus. \(a^{m-2} \bmod m\) is not the inverse when \(m\) isn't prime. If the problem uses a non-prime modulus (rare, but it happens), you need the Extended Euclidean Algorithm from Ch4 L4.

• Forgetting to reduce the numerator in modular division. Writing numerator * modInverse(denominator, prime) % prime when numerator is larger than prime can overflow before the final %. Always reduce first: numerator % prime * modInverse(denominator, prime) % prime.

• Taking the inverse of zero. modInverse(0, prime) silently returns \(0\), which is wrong — zero has no inverse. If your problem involves division by a value that could be zero mod \(p\), handle that case separately.

---

Quick Recap

• The modular inverse of \(a\) is the integer \(a^{-1}\) such that \(a \cdot a^{-1} \equiv 1 \pmod{m}\). It exists exactly when \(\gcd(a, m) = 1\).
• Fermat's Little Theorem: if \(p\) is prime and \(p \nmid a\), then \(a^{p-1} \equiv 1 \pmod{p}\), so \(a^{-1} \equiv a^{p-2} \pmod{p}\).
• Compute via binary exponentiation: modInverse(a, p) = modPow(a, p - 2, p). \(O(\log p)\) time.
• Division under mod becomes multiplication by the inverse: \(a / b \bmod p = a \times b^{p-2} \bmod p\).
• This only works for prime moduli. For composite moduli, use Extended Euclidean (Ch4 L4).

---

Problems

Problem	Link	Difficulty	Focus
CSES — Exponentiation II	cses.fi/problemset/task/1712	Medium	Modular exponentiation with exponent reduction via Fermat
LeetCode 2550 — Count Collisions of Monkeys on a Polygon	leetcode.com/problems/count-collisions-of-monkeys-on-a-polygon	Medium	Modular arithmetic with power of 2 and subtraction under mod

---

Next lesson: Modular Inverse for composite moduli via Extended Euclidean, plus the \(O(n)\) precomputation trick for all inverses from \(1\) to \(n\).