Introduction

Despite the title, this question is usually about computing n! mod m efficiently when m is prime. The prime assumption matters because it gives you strong number-theory tools, and it also creates one very important shortcut: if n is at least m, then n! already contains m as a factor, so the result is immediately zero.

The First Shortcut: n >= m

If m is prime and n >= m, then:

• 'n! includes the factor m'
• any multiple of m is congruent to zero modulo m

So this case is trivial:

1def factorial_mod_prime(n: int, p: int) -> int:
2    if n >= p:
3        return 0
4    result = 1
5    for value in range(2, n + 1):
6        result = (result * value) % p
7    return result
8
9
10print(factorial_mod_prime(5, 11))
11print(factorial_mod_prime(11, 11))

Output:

10
0

For many inputs, this early exit is the whole optimization.

The Straightforward Method for n < p

When n < p, the simplest correct method is to multiply from 1 through n and reduce modulo p after each step.

1def factorial_mod_prime(n: int, p: int) -> int:
2    if n >= p:
3        return 0
4
5    result = 1
6    for value in range(2, n + 1):
7        result = (result * value) % p
8
9    return result

This runs in O(n) time and is usually the right answer unless n is extremely large and still smaller than p.

The per-step modulo keeps intermediate values small, so you never need to build the full factorial.

A Faster Trick When n Is Close to p

If n is just a little smaller than p, Wilson's theorem can be useful. For a prime p:

(p - 1)! ≡ -1 mod p

That lets you rewrite n! in terms of the tail from n + 1 to p - 1. Instead of multiplying all the way from 1 to n, you multiply the shorter missing tail and divide it out modulo p.

Because modular division under a prime modulus is multiplication by an inverse, you can compute those inverses with fast exponentiation.

1def mod_inverse(a: int, p: int) -> int:
2    return pow(a, p - 2, p)
3
4
5def factorial_mod_prime_fast_when_close(n: int, p: int) -> int:
6    if n >= p:
7        return 0
8
9    if n <= p // 2:
10        result = 1
11        for value in range(2, n + 1):
12            result = (result * value) % p
13        return result
14
15    tail_product = 1
16    for value in range(n + 1, p):
17        tail_product = (tail_product * value) % p
18
19    return (-mod_inverse(tail_product, p)) % p
20
21
22print(factorial_mod_prime_fast_when_close(9, 11))

For n = 9 and p = 11, this is convenient because you only deal with the missing factor 10 instead of multiplying 1 through 9.

How to Choose Between the Two Methods

If n is small, the ordinary iterative product is simple and fast. If n is very close to p, Wilson's theorem can reduce the work from roughly n steps to roughly p - n steps.

So the practical rule is:

• if n >= p, return 0
• if n is much smaller than p, multiply from 1 to n
• if n is very close to p, use Wilson's theorem and modular inverses

That gives you an efficient algorithm without unnecessary complexity.

Common Pitfalls

The biggest mistake is forgetting the n >= p shortcut. Once p appears as a factor of n!, the answer is zero, and no further work is needed.

Another pitfall is trying to compute n! directly before taking the modulus. Factorials grow extremely quickly, so the whole point is to reduce after each multiplication.

Developers also misuse Fermat's little theorem by applying modular inverses under a modulus that is not prime. The inverse formula using a^(p-2) only works cleanly in this context because the modulus is prime and the value being inverted is not divisible by it.

Finally, do not overcomplicate the problem. For one-off computations with moderate n, the simple linear loop is often the best real-world solution.

Summary

• If the goal is n! mod p and n >= p, the result is immediately 0.
• For n < p, the standard iterative product with per-step modulo runs in O(n).
• When n is close to p, Wilson's theorem can reduce the amount of multiplication.
• Modular inverses under a prime modulus can be computed with fast exponentiation.
• The simplest method is usually best unless n is specifically near the prime modulus.