Skip to content

Modular Inverse: General Case and Precomputation

Pillar: Chain — "Each inverse depends on the previous: \(\text{inv}[i] = -(m/i) \times \text{inv}[m \bmod i] \bmod m\). This IS a chain recurrence." Pillar: Fix — "When \(m\) isn't prime, fix \(ax \equiv 1 \pmod{m}\) and solve via Extended Euclidean."

The Setup

Ch4 L3 gave you one tool: Fermat's Little Theorem. It computes \(a^{-1} \bmod p\) in \(O(\log p)\), but only when \(p\) is prime. Two gaps remain.

First, what if \(m\) is not prime? Problems with moduli like \(10^6\), \(998244352\) (prime, fine), or arbitrary \(m\) given as input all show up in contest and interview settings. Fermat doesn't apply when \(m\) is composite.

Second, what if you need the inverses of \(1, 2, 3, \ldots, n\) all at once? Computing each one individually via Fermat or Extended GCD costs \(O(n \log m)\). There's a recurrence that does it in \(O(n)\) — one multiplication per value.

This lesson fills both gaps.

When \(m\) Is Not Prime

The equation you're solving is \(ax \equiv 1 \pmod{m}\). Rewrite it: \(ax + my = 1\) for some integer \(y\). This is exactly Bezout's identity from Ch3 L3. The Extended Euclidean algorithm finds \(x\) and \(y\).

An inverse exists if and only if \(\gcd(a, m) = 1\). When \(\gcd(a, m) > 1\), the left side \(ax + my\) is always a multiple of \(\gcd(a, m)\), so it can never equal \(1\).

Worked Example: \(3^{-1} \bmod 10\)

Solve \(3x \equiv 1 \pmod{10}\), i.e., find \(x\) such that \(3x + 10y = 1\).

Run Extended Euclidean on \((10, 3)\):

Step \(a\) \(b\) \(q\) \(r\) Coefficients
0 \(10\) \(3\) \(3\) \(1\) —
1 \(3\) \(1\) \(3\) \(0\) —

Unwind:

\[1 = 10 - 3 \times 3\]

So \(x = -3\) for variable \(a = 3\), meaning \(3 \times (-3) + 10 \times 1 = -9 + 10 = 1\). Check.

Reduce: \(x = -3 \equiv 7 \pmod{10}\).

Verify: \(3 \times 7 = 21 = 2 \times 10 + 1\), so \(21 \bmod 10 = 1\). Confirmed: \(3^{-1} \bmod 10 = 7\).

The Algorithm

Extract the coefficient of \(a\) from the Extended Euclidean algorithm. If \(\gcd(a, m) \neq 1\), no inverse exists — return \(-1\) or signal an error.

long long modInverseExtGCD(long long value, long long mod) {
    long long oldRemainder = value, newRemainder = mod;
    long long oldCoefficient = 1, newCoefficient = 0;
    while (newRemainder != 0) {
        long long quotient = oldRemainder / newRemainder;
        long long tempRemainder = newRemainder;
        newRemainder = oldRemainder - quotient * newRemainder;
        oldRemainder = tempRemainder;
        long long tempCoefficient = newCoefficient;
        newCoefficient = oldCoefficient - quotient * newCoefficient;
        oldCoefficient = tempCoefficient;
    }
    if (oldRemainder != 1) return -1;
    return (oldCoefficient % mod + mod) % mod;
}

\(O(\log(\min(a, m)))\) time, \(O(1)\) space.

This is the same Extended GCD from Ch3 L3, but we only track the coefficient for \(a\) (not \(b\)), and we reduce the result into \([0, m)\).

Precomputing All Inverses \(1\) to \(n\) in \(O(n)\)

This is the centerpiece of the lesson. You need the inverse of every integer from \(1\) to \(n\) modulo a prime \(m\). Computing each one via Fermat costs \(O(\log m)\) per value, for \(O(n \log m)\) total. The chain recurrence does it in \(O(n)\).

The Derivation

Start with the division algorithm. Write \(m\) divided by \(i\):

\[m = \left\lfloor \frac{m}{i} \right\rfloor \cdot i + (m \bmod i)\]

Let \(q = \lfloor m/i \rfloor\) and \(r = m \bmod i\). So \(m = qi + r\).

Take this equation modulo \(m\). The left side vanishes:

\[0 \equiv qi + r \pmod{m}\]

Rearrange:

\[qi \equiv -r \pmod{m}\]

Multiply both sides by \(i^{-1} \cdot r^{-1}\) (both exist because \(m\) is prime and \(1 \leq i, r < m\)):

\[q \cdot r^{-1} \equiv -i^{-1} \pmod{m}\]

Therefore:

\[i^{-1} \equiv -q \cdot r^{-1} \pmod{m}\]

Substitute back \(q = \lfloor m/i \rfloor\) and \(r = m \bmod i\):

\[\boxed{\text{inv}[i] = -\left\lfloor \frac{m}{i} \right\rfloor \cdot \text{inv}[m \bmod i] \bmod m}\]

Since \(m \bmod i < i\), the right side references an inverse we've already computed. That's the chain: each value depends on a strictly earlier one.

Base Case

\(\text{inv}[1] = 1\), because \(1 \times 1 \equiv 1 \pmod{m}\) for any \(m\).

Trace Table: Inverses Mod 7

Walk through \(i = 1\) to \(6\) with \(m = 7\).

\(i\) \(\lfloor 7/i \rfloor\) \(7 \bmod i\) \(\text{inv}[7 \bmod i]\) \(\text{inv}[i] = (7 - \lfloor 7/i \rfloor \times \text{inv}[7 \bmod i] \bmod 7) \bmod 7\) Verify: \(i \times \text{inv}[i] \bmod 7\)
\(1\) \(7\) \(0\) — (base) \(1\) \(1 \times 1 = 1\)
\(2\) \(3\) \(1\) \(\text{inv}[1] = 1\) \((7 - 3 \times 1 \bmod 7) \bmod 7 = (7 - 3) \bmod 7 = 4\) \(2 \times 4 = 8 \equiv 1\)
\(3\) \(2\) \(1\) \(\text{inv}[1] = 1\) \((7 - 2 \times 1 \bmod 7) \bmod 7 = (7 - 2) \bmod 7 = 5\) \(3 \times 5 = 15 \equiv 1\)
\(4\) \(1\) \(3\) \(\text{inv}[3] = 5\) \((7 - 1 \times 5 \bmod 7) \bmod 7 = (7 - 5) \bmod 7 = 2\) \(4 \times 2 = 8 \equiv 1\)
\(5\) \(1\) \(2\) \(\text{inv}[2] = 4\) \((7 - 1 \times 4 \bmod 7) \bmod 7 = (7 - 4) \bmod 7 = 3\) \(5 \times 3 = 15 \equiv 1\)
\(6\) \(1\) \(1\) \(\text{inv}[1] = 1\) \((7 - 1 \times 1 \bmod 7) \bmod 7 = (7 - 1) \bmod 7 = 6\) \(6 \times 6 = 36 \equiv 1\)

Every product checks out. The pattern \(\text{inv}[i] + \text{inv}[7 - i] = 7\) is no coincidence — it follows from \(i^{-1} + (m-i)^{-1} \equiv 0 \pmod{m}\).

The Code

vector<long long> precomputeInverses(int limit, long long mod) {
    vector<long long> inverse(limit + 1, 0);
    inverse[1] = 1;
    for (int i = 2; i <= limit; i++) {
        inverse[i] = (mod - (mod / i) * inverse[mod % i] % mod) % mod;
    }
    return inverse;
}

\(O(n)\) time, \(O(n)\) space.

The expression mod - (mod / i) * inverse[mod % i] % mod implements \(-\lfloor m/i \rfloor \cdot \text{inv}[m \bmod i] \bmod m\) without ever going negative. The outer mod - replaces the negation, and the final % mod handles the case where the subtraction equals exactly \(m\) (producing \(0\)).

Precomputed Factorials (Preview)

Many combinatorics problems (starting in Ch5) need \(n! \bmod m\) for various \(n\). The idea is simple: build a table where \(\text{fact}[i] = i! \bmod m\) using the recurrence \(\text{fact}[i] = \text{fact}[i-1] \times i \bmod m\). This is \(O(n)\) time and \(O(n)\) space.

To compute \(\binom{n}{k} \bmod m\), you'll also need inverse factorials — a second table built using a single modpow call and a backward loop. Ch5 L2 teaches the complete factorial + inverse factorial precomputation as a single unit, after introducing the combinatorial identities that motivate it. That's where you'll write the code.

Decision Table: Which Method When?

Scenario Method Time Constraint
Single inverse, \(m\) is prime Fermat: \(a^{m-2} \bmod m\) (Ch4 L3) \(O(\log m)\) \(\gcd(a, m) = 1\), \(m\) prime
Single inverse, \(m\) arbitrary Extended GCD: solve \(ax + my = 1\) \(O(\log m)\) \(\gcd(a, m) = 1\)
All inverses \(1\) to \(n\), \(m\) prime Chain recurrence \(O(n)\) \(m\) prime, \(n < m\)
\(n!\) for all \(n\) up to limit Factorial precomputation \(O(n)\) —
\(\binom{n}{k} \bmod m\) for many queries Factorial + inverse factorial (Ch5 L2) \(O(n)\) precompute, \(O(1)\) query \(m\) prime

The default competitive programming modulus \(10^9 + 7\) is prime, so Fermat and the chain recurrence both apply. Use Extended GCD only when the problem gives an arbitrary (possibly composite) modulus.

One subtlety: the chain recurrence requires \(m\) to be prime. If \(m\) is composite, \(m \bmod i\) might share a factor with \(m\), and \(\text{inv}[m \bmod i]\) wouldn't exist. For composite moduli, compute inverses individually via Extended GCD (only for values coprime to \(m\)).

The Code (Complete)

All three functions together:

#include <bits/stdc++.h>
using namespace std;

long long modInverseExtGCD(long long value, long long mod) {
    long long oldRemainder = value, newRemainder = mod;
    long long oldCoefficient = 1, newCoefficient = 0;
    while (newRemainder != 0) {
        long long quotient = oldRemainder / newRemainder;
        long long tempRemainder = newRemainder;
        newRemainder = oldRemainder - quotient * newRemainder;
        oldRemainder = tempRemainder;
        long long tempCoefficient = newCoefficient;
        newCoefficient = oldCoefficient - quotient * newCoefficient;
        oldCoefficient = tempCoefficient;
    }
    if (oldRemainder != 1) return -1;
    return (oldCoefficient % mod + mod) % mod;
}

vector<long long> precomputeInverses(int limit, long long mod) {
    vector<long long> inverse(limit + 1, 0);
    inverse[1] = 1;
    for (int i = 2; i <= limit; i++) {
        inverse[i] = (mod - (mod / i) * inverse[mod % i] % mod) % mod;
    }
    return inverse;
}

vector<long long> precomputeFactorials(int limit, long long mod) {
    vector<long long> factorial(limit + 1);
    factorial[0] = 1;
    for (int i = 1; i <= limit; i++) {
        factorial[i] = factorial[i - 1] * i % mod;
    }
    return factorial;
}

Common Mistakes

  • Forgetting the negation in the chain recurrence. Writing (mod / i) * inverse[mod % i] % mod without the negation gives a wrong value that still looks plausible. The formula has a minus sign — implement it as mod - (...) to avoid negative intermediate values.

  • Using the chain recurrence with composite \(m\). The derivation divides by \(r = m \bmod i\), which requires \(\gcd(r, m) = 1\). When \(m\) is composite, this can fail silently — the recurrence produces garbage without any runtime error. Only use it when \(m\) is prime.

  • Calling Extended GCD when \(\gcd(a, m) \neq 1\) and not checking. The function returns \(-1\) when no inverse exists, but if you ignore the return value and use it as a valid inverse, you'll get wrong answers. Always check or ensure \(\gcd(a, m) = 1\) before using the result.

Quick Recap

  • Extended GCD computes \(a^{-1} \bmod m\) for any \(m\) (not just primes), as long as \(\gcd(a, m) = 1\). Runs in \(O(\log m)\).
  • The chain recurrence \(\text{inv}[i] = -\lfloor m/i \rfloor \cdot \text{inv}[m \bmod i] \bmod m\) precomputes all inverses from \(1\) to \(n\) in \(O(n)\). Requires \(m\) prime.
  • Factorial precomputation builds \(i! \bmod m\) for \(i = 0\) to \(n\) in \(O(n)\). Combine with inverse factorials (Ch5 L2) for fast \(\binom{n}{k}\) queries.
  • Use Fermat (\(a^{m-2}\)) for one-off inverses with prime \(m\). Use Extended GCD for composite \(m\). Use the chain recurrence when you need all inverses \(1\) to \(n\).

Problems

Problem Link Difficulty Focus
CSES — Binomial Coefficients cses.fi/problemset/task/1079 Medium Precomputed factorials + inverse factorials (preview of Ch5 L2)

Next lesson: Euler's Totient Function — counting integers coprime to \(n\), and generalizing Fermat's theorem to composite moduli.