What Is the Modular Inverse? How Division Works Under a Modulus

You're computing C(100, 50) modulo 10^9+7. The formula is n! divided by k!(n-k)!. Division. Under a modulus. Your brain says this is illegal. Half the internet says this is impossible.

It isn't. The modular inverse turns division into multiplication, and it shows up in nearly every combinatorics problem that asks for an answer "modulo a prime." Here's what it is, how to compute it, and why it breaks people in interviews.

Division Breaks Under a Modulus

Regular arithmetic has one clean property everyone takes for granted: (a / b) * b = a. Always. Math teachers love this. Modular arithmetic does not.

You can add, subtract, and multiply under a modulus and stay in integer territory. Division breaks that because a / b might not be an integer at all, and modular arithmetic only works on integers. Try to divide 7 by 3 under mod 10 and you get 2.33... The system rejects you. No fractional numbers allowed.

The moment you need to divide under a modulus, you need a different tool. That tool is the modular inverse, and it quietly saves every combinatorics problem that would otherwise be unsolvable.

Modular arithmetic, to you, when you declare division impossible.

Division by Multiplication

The modular inverse of a modulo m is a number x such that:

a * x ≡ 1 (mod m)

Written in shorthand: x = a⁻¹ (mod m). Once you have it, you replace (result / a) mod m with (result * a⁻¹) mod m. Division disappears. You're back to multiplication, which modular arithmetic is perfectly happy with.

Concrete example: what is the modular inverse of 3 modulo 7?

You want x such that 3 * x ≡ 1 (mod 7). Try each value:

x	3 * x	(3 * x) mod 7
1	3	3
2	6	6
3	9	2
4	12	5
5	15	1

So 3⁻¹ ≡ 5 (mod 7). Wherever you'd divide by 3, you multiply by 5 instead. This is brute force, and it works fine for tiny examples. For actual interviews you want something faster.

When Does a Modular Inverse Exist?

The modular inverse of a modulo m exists if and only if gcd(a, m) = 1. The two numbers must be coprime.

Try 2 modulo 4: 2 * 1 = 2, 2 * 2 ≡ 0, 2 * 3 ≡ 2. You cycle through {2, 0, 2, 0} forever and never hit 1. No inverse exists.

In coding interviews, this almost never matters. The modulus is almost always a prime like 10^9+7, and every integer from 1 to p-1 is coprime to a prime. Inverses always exist for any value you'd care about. The mod 1000000007 convention exists precisely because prime moduli make inverses safe to compute.

Use Fermat's Little Theorem When the Modulus Is Prime

Yes, there are a lot of famous theorems in number theory. This one is actually useful.

When m is prime, Fermat's Little Theorem states:

a^(m-1) ≡ 1 (mod m)    for any a not divisible by m

Rearrange: a * a^(m-2) ≡ 1 (mod m). So a⁻¹ ≡ a^(m-2) (mod m).

Raise a to the power m-2, modulo m. With binary exponentiation, this runs in O(log m) time. For m = 10^9+7, you're doing about 30 multiplications. Fast.

In Python, one line does it:

def mod_inverse(a: int, p: int) -> int:
    return pow(a, p - 2, p)

Python's three-argument pow(a, b, mod) uses binary exponentiation internally and handles arbitrarily large integers. This is one of those cases where Python's standard library quietly did the hard work for you.

In Java, you write the exponentiation yourself unless you're on Java 17+ with BigInteger.modPow:

long modInverse(long a, long p) {
    return modPow(a, p - 2, p);
}

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

Use Extended Euclidean When the Modulus Isn't Prime

Fermat requires a prime modulus. When m is not prime, it fails silently. The Extended Euclidean Algorithm is the general-purpose fix.

The standard Euclidean GCD algorithm computes gcd(a, m). The extended version also finds integers x and y satisfying Bezout's identity:

a * x + m * y = gcd(a, m)

When gcd(a, m) = 1, this becomes a * x + m * y = 1. Take both sides modulo m. The m * y term vanishes, leaving a * x ≡ 1 (mod m). So x is the inverse. You computed it as a side effect of running GCD.

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

def mod_inverse_general(a: int, m: int) -> int:
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError("modular inverse does not exist")
    return x % m

The x % m at the end is not optional. The extended GCD can return a negative x, which is mathematically valid but will blow up any code that assumes a positive result. Taking the result modulo m maps it into [0, m-1].

Both methods run in O(log m) time. Fermat for prime moduli. Extended Euclidean for everything else.

Precompute All Modular Inverses Up to N in O(n)

Sometimes you need modular inverses for all integers from 1 to n, not just one. Computing each via Fermat costs O(n log m) total. There's a linear recurrence that brings this down to O(n), and it's one of those tricks that looks like magic until you see the derivation.

MOD = 10**9 + 7

def precompute_inverses(n: int) -> list[int]:
    inv = [0] * (n + 1)
    inv[1] = 1
    for i in range(2, n + 1):
        inv[i] = -(MOD // i) * inv[MOD % i] % MOD
    return inv

The derivation: write MOD = q * i + r where q = MOD // i and r = MOD % i. Rearranging modulo MOD gives i⁻¹ ≡ -q * r⁻¹ (mod MOD). Since r < i, you've already computed inv[r] by the time you need it. This linear precomputation is what makes factorial inverse tables efficient. Solutions that precompute both factorials[] and inv_factorials[] before answering queries are using exactly this trick.

How This Shows Up in Interviews

Modular inverse appears in one dominant pattern: computing modular arithmetic expressions that involve division, usually binomial coefficients.

C(n, k) = n! / (k! * (n-k)!)

To compute this modulo a prime p, precompute factorials up to n and their inverses. Then each combination query is O(1):

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

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

inv_factorials = [1] * MAX
inv_factorials[MAX - 1] = pow(factorials[MAX - 1], MOD - 2, MOD)
for i in range(MAX - 2, -1, -1):
    inv_factorials[i] = inv_factorials[i + 1] * (i + 1) % MOD

def comb(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    return factorials[n] * inv_factorials[k] % MOD * inv_factorials[n - k] % MOD

The backward pass builds inv_factorials from the top down. You compute one expensive inverse at position MAX-1, then unwind using inv_factorials[i] = inv_factorials[i+1] * (i+1) % MOD. One call to pow, then O(n) multiplications. Clean.

The second common pattern: a problem gives you a rational answer and asks for the numerator times the denominator's inverse, modulo p. Numerator and denominator separately, then:

# (p / q) mod MOD
result = p % MOD * pow(q, MOD - 2, MOD) % MOD

Whenever a problem gives you a fraction and a prime modulus, this is the formula. The hard part is recognizing you need it in the first place.

This is where candidates stumble. Knowing that a^(p-2) gives you the inverse is one thing. Explaining why it works under time pressure, in complete sentences, while writing code, is another. If you want to practice talking through modular inverse while you code, SpaceComplexity runs voice-based mock interviews that score your reasoning as you go, not just whether the code ran.

Complexity

Method	Time	Space	Works When
Fermat's Little Theorem	O(log p)	O(1)	p is prime
Extended Euclidean	O(log m)	O(log m) recursive, O(1) iterative	gcd(a, m) = 1
Linear precomputation	O(n)	O(n)	Need inverses for 1..n, p prime

Further Reading

• Modular multiplicative inverse, Wikipedia
• Fermat's Little Theorem, Wikipedia
• Modular inverse, cp-algorithms.com
• Extended Euclidean Algorithm, cp-algorithms.com
• Modular Multiplicative Inverse, GeeksforGeeks