Loading…

hardMath GeometryRarely asked

Lucas' Theorem

Q: How do you solve Lucas' Theorem using the Factorial + Fermat Inverse (Baseline — fails when n ≥ p) approach?

When to use it: Mention first to show you know the standard method AND precisely why it breaks once n ≥ p — that diagnosis motivates Lucas. The textbook method computes `C(n, r) mod p = fact[n]·invFact[r]·invFact[n−r] mod p`, with inverse-factorials from Fermat's little theorem. It is the correct, fast answer **when `p > n`**. The point of this baseline is to see exactly why it fails outside that regime. **Failure 1 — the table can't exist.** With `n` up to `10¹⁸`, a factorial array of length `n+1` is impossible to allocate. There isn't enough memory in the universe for `10¹⁸` entries. **Failure 2 — the factorial has no inverse.** Even setting memory aside, the math breaks. Once `n ≥ p`, the product `n! = 1·2·…·n` includes the factor `p` itself, so `n! ≡ 0 (mod p)`. A value of `0` modulo `p` has **no** multiplicative inverse — Fermat's `a^(p−2)` gives `0`, not a true inverse. The formula `fact[n]·invFact[r]·…` would multiply and 'invert' zeros and produce garbage. This is the deep reason the method is restricted to `p > n`, where no factorial argument ever reaches `p`. **What we actually need.** A method whose every factorial argument stays **below `p`**, so no factor of `p` ever enters and every inverse exists. Lucas' theorem delivers exactly that by working on the base-`p` digits of `n` and `r`, each of which is in `[0, p)`. Time complexity: O(n) precompute, O(1) query (when valid). Space complexity: O(n).

Math & Number Theory · 25 of 36 · 12 min

Given integers n and r and a prime p, compute the binomial coefficient C(n, r) mod p.

The twist versus the standard problem: n may be much larger than `p` (for example n up to 10¹⁸ with p a small prime like 13 or 1000003). The usual 'precompute factorials up to n' approach is impossible (n is too large) and incorrect (factorials contain factors of p). Use Lucas' theorem.

In plain English

When p > n, C(n, r) mod p is just the factorial-inverse formula. But when n ≥ p, that formula is both infeasible (you can't build a length-n factorial table for n = 10¹⁸) and invalid (n! contains factors of p, so n! ≡ 0 mod p and has no inverse). Lucas' theorem provides a different route: it relates C(n, r) mod p to the binomial coefficients of the digits of n and r when both are written in base p. Each digit is below p, so each per-digit binomial is computable with a small factorial table. Multiplying them gives the answer mod p.

Examples

Example 1

Input: n = 10, r = 3, p = 3
Output: 0
Note: Base 3: 10 = (1 0 1)₃, 3 = (0 1 0)₃. Digit-wise: C(1,0)·C(0,1)·C(1,0). The middle factor C(0,1) = 0 → whole product 0. (Indeed C(10,3)=120, and 120 mod 3 = 0.)

Example 2

Input: n = 1000, r = 500, p = 13
Output: 0
Note: At least one base-13 digit of 500 exceeds the matching digit of 1000, making a factor 0 (C(1000,500) mod 13 = 0).

Example 3

Input: n = 5, r = 2, p = 13
Output: 10
Note: n, r < p so there's a single digit: C(5,2) = 10, and 10 mod 13 = 10. Lucas reduces to the ordinary binomial here.

Constraints

0 ≤ r ≤ n ≤ 10¹⁸ (n can vastly exceed p)
p is prime and 2 ≤ p ≤ 10⁶ or so (small enough to precompute factorials up to p−1)
Define C(n, r) = 0 when r > n
Use long in Java for digit products; Python big ints are exact

Clarifying questions4First question: Is n larger than p?Explore questions

Q1.Is n larger than p?
That's the whole reason for Lucas. If p > n I'd just use factorials + Fermat. When n ≥ p, those factorials hit a factor of p and the method collapses, so I switch to Lucas.
Q2.Is p prime?
Lucas requires a prime modulus. For a prime power I'd use Granville's generalisation; for a general composite I'd factor it, apply Lucas per prime power, and combine with CRT.
Q3.How small is p — can I precompute factorials up to p−1?
Yes, p is small (say ≤ 10⁶), so I build fact[0..p−1] and inverse-factorials once with Fermat, then each digit's binomial is O(1).
Q4.What if r > n?
C(n, r) = 0. Lucas also returns 0 whenever any base-p digit of r exceeds the corresponding digit of n — I short-circuit there.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The factorial-inverse method for nCr mod p assumes p > n. When n can be far larger than p (and p is small), that breaks — fact[n] mod p hits a factor of p and becomes 0, so its inverse doesn't exist. Lucas' theorem rescues this: write n and r in base p as digits (nₖ…n₁n₀) and (rₖ…r₁r₀). Then C(n, r) ≡ ∏ C(nᵢ, rᵢ) (mod p) — the product of the small digit-wise binomials. Each C(nᵢ, rᵢ) has both arguments < p, so the standard factorial+Fermat method (or a tiny table) computes it. If any digit has rᵢ > nᵢ, that factor is 0, so the whole answer is 0.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise that the factorial-inverse nCr method requires p > n, why it fails when n ≥ p (fact[n] ≡ 0 mod p has no inverse), and that Lucas' theorem decomposes the coefficient into digit-wise binomials in base p.

Where candidates slip

Applying the factorial method with n ≥ p (division by a non-invertible factorial), forgetting that rᵢ > nᵢ in any digit makes the whole result 0, or using Lucas with a non-prime modulus.

How to stand out

Explain WHY n ≥ p breaks the factorial method, state Lucas as C(n,r) ≡ ∏ C(nᵢ,rᵢ) (mod p), note the 0 short-circuit, and mention CRT-over-primes for composite moduli.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Factorial + Fermat Inverse (Baseline — fails when n ≥ p)	`O(n) precompute, O(1) query (when valid)`	`O(n)`	Mention first to show you know the standard method AND precisely why it breaks once n ≥ p — that diagnosis motivates Lucas.	Read
2	Lucas' Theorem (Optimal)Optimal	`O(p + log_p(n)) — O(p) precompute, O(log_p n) digits per query`	`O(p)`	The answer they want when n can exceed a small prime p. Phrase it as 'write n and r in base p; the coefficient is the product of the digit binomials'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewlucas(n, r, p)r == 0 ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Factorial + Fermat Inverse (Baseline — fails when n ≥ p)

TimeO(n) precompute, O(1) query (when valid)SpaceO(n)

Mention first to show you know the standard method AND precisely why it breaks once n ≥ p — that diagnosis motivates Lucas.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The standard nCr mod p uses fact[n]·invFact[r]·invFact[n−r] with Fermat inverses. What two things go wrong when n is 10¹⁸ and p is small?

2Hint 2Explore hint

First, you can't allocate a factorial table of length 10¹⁸. Second — subtler — once n ≥ p, n! is divisible by p, so fact[n] ≡ 0 mod p and has NO inverse.

3Hint 3Explore hint

So the method is both infeasible and mathematically invalid here. You need a formula that works digit-by-digit in base p, keeping every factorial argument below p.

A · Core idea

The textbook method computes C(n, r) mod p = fact[n]·invFact[r]·invFact[n−r] mod p, with inverse-factorials from Fermat's little theorem. It is the correct, fast answer when `p > n`. The point of this baseline is to see exactly why it fails outside that regime.

Failure 1 — the table can't exist. With n up to 10¹⁸, a factorial array of length n+1 is impossible to allocate. There isn't enough memory in the universe for 10¹⁸ entries.

Failure 2 — the factorial has no inverse. Even setting memory aside, the math breaks. Once n ≥ p, the product n! = 1·2·…·n includes the factor p itself, so n! ≡ 0 (mod p). A value of 0 modulo p has no multiplicative inverse — Fermat's a^(p−2) gives 0, not a true inverse. The formula fact[n]·invFact[r]·… would multiply and 'invert' zeros and produce garbage. This is the deep reason the method is restricted to p > n, where no factorial argument ever reaches p.

What we actually need. A method whose every factorial argument stays below `p`, so no factor of p ever enters and every inverse exists. Lucas' theorem delivers exactly that by working on the base-p digits of n and r, each of which is in [0, p).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10, r = 3, p = 3

build fact

fact[3] = 6 ≡ 0 (mod 3)

Statealready a zero

Final resultmethod invalid for n ≥ p

C · Code with teaching comments

Reference implementation preview// Valid ONLY when p > n. Shown to expose the failure mode for n >= p. public long nCrFactorial(int n, int r, long p, long[] fact, long[] invFact) { if (r < 0 || r > n) return 0; // If n >= p, fact[n] % p == 0 (no inverse) and the table can't even be built for huge n. return fact[n] * invFact[r] % p * invFact[n - r] % p;Explore the full code

solution.javaJava

Factorial + Fermat Inverse (Baseline — fails when n ≥ p) — reference

1 teaching note

1
// Valid ONLY when p > n. Shown to expose the failure mode for n >= p.
2
public long nCrFactorial(int n, int r, long p, long[] fact, long[] invFact) {
3
    if (r < 0 || r > n) return 0;
4
    // If n >= p, fact[n] % p == 0 (no inverse) and the table can't even be built for huge n.
5
    // Correct only if p > n; when n ≥ p, fact[n] ≡ 0 mod p so invFact is bogus and this
6
    // is invalid.
7
    return fact[n] * invFact[r] % p * invFact[n - r] % p;
8
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.8 lines

D · Why it works and complexityO(n) precompute, O(1) query (when valid) timeO(n) spaceOpen the invariant and proofExplore the proof

This baseline is the right tool only when p > n. The instant n ≥ p it fails twice over — the table is unbuildable and fact[n] ≡ 0 mod p is non-invertible. Diagnosing those two failures is what tells you to reach for Lucas, which keeps every factorial argument under p.

ComplexityO(n) precompute, O(1) query (when valid) time, O(n) space — Precomputing fact[0..n] is O(n) time and space, with O(1) per query — but only when p > n. When n ≥ p the table is too large to build and fact[n] is 0 mod p (not invertible), so the approach simply doesn't work.

E · Edge cases and pitfalls3Using it when n ≥ p — fact[n] ≡ 0 mod p is not invertible.Explore edge cases

Pitfalls

Using it when n ≥ p — fact[n] ≡ 0 mod p is not invertible.
Trying to allocate a factorial table for n = 10¹⁸.
Assuming Fermat gives an inverse of 0 — it returns 0, not a real inverse.

03.2

Approach 2 of 2 · Optimal

Lucas' Theorem (Optimal)

TimeO(p + log_p(n)) — O(p) precompute, O(log_p n) digits per querySpaceO(p)

The answer they want when n can exceed a small prime p. Phrase it as 'write n and r in base p; the coefficient is the product of the digit binomials'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write n and r in base p. Lucas' theorem says C(n, r) ≡ ∏ C(nᵢ, rᵢ) (mod p) over the base-p digits. Each digit is < p — what does that buy you?

2Hint 2Explore hint

Precompute factorials and inverse-factorials only up to p−1 (one Fermat inverse + backward sweep). Then each digit's C(nᵢ, rᵢ) is O(1).

3Hint 3Explore hint

Peel digits with n % p and r % p, multiply the digit binomials, recurse on n / p and r / p. If any rᵢ > nᵢ the digit binomial is 0, so the whole answer is 0 — short-circuit.

A · Core idea

Lucas' theorem reduces a binomial coefficient modulo a prime to a product of much smaller binomials — the binomials of the base-p digits.

The statement. Write n and r in base p:

n = nₖ·pᵏ + … + n₁·p + n₀, r = rₖ·pᵏ + … + r₁·p + r₀, with each digit in [0, p). Then

C(n, r) ≡ C(nₖ, rₖ) · … · C(n₁, r₁) · C(n₀, r₀) (mod p).

Every factor C(nᵢ, rᵢ) has both arguments below p, so no factorial argument ever reaches p — the inverse problem that killed the baseline never arises.

Why each digit binomial is cheap. Since nᵢ, rᵢ < p, precompute fact[0..p−1] and inverse-factorials up to p−1 once (one Fermat inverse for fact[p−1], then the backward sweep), and C(nᵢ, rᵢ) = fact[nᵢ]·invFact[rᵢ]·invFact[nᵢ−rᵢ] mod p is O(1). The setup is O(p), not O(n) — that's what makes huge n feasible.

Why a 0 digit zeroes everything. If for some position rᵢ > nᵢ, then C(nᵢ, rᵢ) = 0 (you can't choose more than you have), and a single zero factor makes the entire product 0 mod p. So the algorithm can short-circuit and return 0 the moment it sees rᵢ > nᵢ. This is why coefficients like C(10, 3) mod 3 come out 0: a base-3 digit of 3 exceeds the matching digit of 10.

The recursion. Peel the lowest digits with nᵢ = n % p, rᵢ = r % p; multiply the running product by C(nᵢ, rᵢ); recurse (or loop) on n / p, r / p. Stop when r becomes 0 — all higher digits of r are 0, and C(anything, 0) = 1, so they contribute nothing. There are only O(log_p n) digits, so a query is fast even for n = 10¹⁸.

Why p must be prime. Lucas' theorem is a statement modulo a prime; the proof uses (1 + x)^p ≡ 1 + x^p (mod p), the Freshman's-dream identity that holds only for prime p. For a prime power p^a there's Granville's generalisation; for a general composite, factor it, apply Lucas modulo each prime (power), and recombine with the Chinese Remainder Theorem.

Overflow safety. Digit binomials are products of values below p; with p up to ~10⁶ the products fit comfortably in a 64-bit long as long as you reduce mod p after each multiply. Python integers are unbounded, so the modulus is for correctness and speed, not overflow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10, r = 3, p = 3

Array state

digits

n=(1,0,1)₃, r=(0,1,0)₃ (low→high)

digit ↓

n0=1,r0=0

[0]

n1=0,r1=1

[1]

n2=1,r2=0

[2]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Lucas' Theorem (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
class Lucas {
4
    private final long p;
5
    private final long[] fact, invFact;
6
 
7
    Lucas(long p) {
8
        this.p = p;
9
        int sz = (int) p;
10
        fact = new long[sz];
11
        invFact = new long[sz];
12
        fact[0] = 1 % p;
13
        // Factorials only up to p−1 — O(p) setup, NOT O(n); this is what makes huge n
14
        // feasible.
15
        for (int i = 1; i < sz; i++) fact[i] = fact[i - 1] * i % p;
16
        // One Fermat inverse seeds the inverse-factorial table.
17
        invFact[sz - 1] = modpow(fact[sz - 1], p - 2, p);
18
        for (int i = sz - 2; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % p;
19
    }
20
 
21
    // C(ni, ri) mod p for digits below p.
22
    private long smallNcr(long n, long r) {
23
        if (r < 0 || r > n) return 0;
24
        return fact[(int) n] * invFact[(int) r] % p * invFact[(int) (n - r)] % p;
25
    }
26
 
27
    long nCr(long n, long r) {
28
        long result = 1 % p;
29
        while (r > 0 || n > 0) {
30
            // Lowest base-p digits of n and r.
31
            long ni = n % p, ri = r % p;
32
            if (ri > ni) return 0;           // digit binomial 0 -> whole answer 0
33
            // Multiply in this digit's binomial, reduced mod p so the long stays
34
            // bounded.
35
            result = result * smallNcr(ni, ri) % p;
36
            // Shift to the next base-p digit; loop runs O(log_p n) times.
37
            n /= p; r /= p;
38
        }
39
        return result;
40
    }
41
 
42
    private long modpow(long base, long exp, long mod) {
43
        long r = 1 % mod; base %= mod;
44
        while (exp > 0) {
45
            if ((exp & 1) == 1) r = r * base % mod;
46
            base = base * base % mod;
47
            exp >>= 1;
48
        }
49
        return r;
50
    }
51
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.51 lines

D · Why it works and complexityO(p + log_p(n)) — O(p) precompute, O(log_p n) digits per query timeO(p) spaceOpen the invariant and proofExplore the proof

Lucas turns 'huge n, small prime p' into 'a handful of tiny binomials' by reading n and r in base p. The two facts that make it practical: every digit binomial has arguments below p (so a length-p factorial table suffices), and any digit with rᵢ > nᵢ collapses the whole product to 0. It's the natural partner of nCr-mod-p: use factorials+Fermat when p > n, Lucas when p ≤ n, and CRT to glue several primes for composite moduli.

ComplexityO(p + log_p(n)) — O(p) precompute, O(log_p n) digits per query time, O(p) space — Precomputing factorials up to p−1 is O(p) time and space (plus one O(log p) Fermat inverse). A query peels O(log_p n) base-p digits, each costing O(1) via the small tables. So per-query time is O(log_p n) after the O(p) setup.

E · Edge cases and pitfalls9n < p and r < p — Single digit: Lucas reduces to the ordinary C(n, r) mod p.Explore edge cases

Edge cases handled

n < p and r < pSingle digit: Lucas reduces to the ordinary C(n, r) mod p.
r = 0All digits of r are 0, every C(nᵢ, 0) = 1 → result 1.
r > nSome digit has rᵢ > nᵢ (or higher r digits exceed n's) → 0.
p = 2Lucas in base 2 gives Kummer's parity: C(n,r) is odd iff r's bits are a subset of n's.

Pitfalls

Using Lucas with a non-prime modulus — it only holds mod a prime; use Granville + CRT otherwise.
Forgetting the rᵢ > nᵢ short-circuit — must contribute a 0 factor.
Precomputing factorials up to n instead of p−1 — defeats the purpose for huge n.
Stopping the loop too early — continue while either n or r still has digits.
Letting digit products overflow in Java — reduce mod p after each multiply, use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class Lucas { private final long p; private final long[] fact, invFact;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class Lucas {
    private final long p;
    private final long[] fact, invFact;

Lucas(long p) {
        this.p = p;
        int sz = (int) p;
        fact = new long[sz];
        invFact = new long[sz];
        fact[0] = 1 % p;
        for (int i = 1; i < sz; i++) fact[i] = fact[i - 1] * i % p;
        invFact[sz - 1] = modpow(fact[sz - 1], p - 2, p);
        for (int i = sz - 2; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % p;
    }

// C(ni, ri) mod p for digits below p.
    private long smallNcr(long n, long r) {
        if (r < 0 || r > n) return 0;
        return fact[(int) n] * invFact[(int) r] % p * invFact[(int) (n - r)] % p;
    }

long nCr(long n, long r) {
        long result = 1 % p;
        while (r > 0 || n > 0) {
            long ni = n % p, ri = r % p;
            if (ri > ni) return 0;           // digit binomial 0 -> whole answer 0
            result = result * smallNcr(ni, ri) % p;
            n /= p; r /= p;
        }
        return result;
    }

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

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Factorial method with n ≥ p

When n ≥ p, n! contains a factor of p, so fact[n] ≡ 0 (mod p) and has no inverse — Fermat returns 0, not a real inverse. The result is meaningless. Use Lucas, which keeps every factorial argument below p.

Explore the code comparison

Don't write this

# n = 10, p = 3:
return fact[n] * inv_fact[r] % p * inv_fact[n - r] % p  # fact[10] % 3 == 0

Write this instead

lucas = Lucas(p)
return lucas.n_cr(n, r)   # digit-wise binomials, every argument < p

Missing the zero-digit short-circuit

If any base-p digit of r exceeds the matching digit of n, C(nᵢ, rᵢ) = 0 and the full product must be 0. Skipping that check (e.g. clamping) gives a wrong nonzero answer.

Explore the code comparison

Don't write this

long ni = n % p, ri = r % p;
result = result * smallNcr(ni, ri) % p; // smallNcr must return 0 when ri>ni

Write this instead

long ni = n % p, ri = r % p;
if (ri > ni) return 0;                  // explicit short-circuit
result = result * smallNcr(ni, ri) % p;

Lucas on a composite modulus

Lucas' theorem holds modulo a prime (its proof uses (1+x)^p ≡ 1+x^p mod p). For a composite m, factor m into prime powers, apply Lucas/Granville per factor, then CRT-combine.

Explore the code comparison

Don't write this

lucas = Lucas(12)        # 12 is not prime — invalid

Write this instead

# factor 12 = 4 * 3; compute C(n,r) mod 4 (Granville) and mod 3 (Lucas),
# then combine with CRT to get C(n,r) mod 12

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reduce a huge nCr mod a small prime to a product of digit-wise binomials in base p

Code pattern to memorize

write n = (n_k ... n_1 n_0) and r = (r_k ... r_1 r_0) in base p
C(n, r) mod p = product over i of C(n_i, r_i) mod p
if any r_i > n_i: the product (and the answer) is 0
each C(n_i, r_i) with n_i, r_i < p via factorials + Fermat inverse

Rules to remember

1Use Lucas when n can exceed p (p small). The plain factorial method needs p > n; Lucas removes that limit.
2Process n and r digit by digit in base p (repeatedly take % p then /= p). The recursion bottoms out when both reach 0.
3If at any digit rᵢ > nᵢ, then C(nᵢ, rᵢ) = 0, which forces the whole product to 0 — short-circuit and return 0.
4Each per-digit C(nᵢ, rᵢ) has nᵢ, rᵢ < p, so precompute factorials and inverse-factorials up to p−1 once (Fermat inverse) and answer each digit in O(1).
5The modulus must be prime (Lucas is a statement mod a prime). For prime powers use the generalised Granville/Andrew theorem; combine several primes with CRT. Use long in Java for digit products.

Use this pattern when

Compute `C(n, r) mod p` where `n` is astronomically large (up to 10¹⁸) and `p` is a **small prime**
Counting problems mod a small prime where n far exceeds the modulus
Combined with CRT to get nCr modulo a composite by working over its prime factors
Anywhere the plain factorial-inverse method fails because `p ≤ n`

Choose another pattern when

`p > n` (e.g. p = 1e9+7 and n ≤ 1e6) → the plain factorial + Fermat method is simpler and direct
The modulus is **not prime** → Lucas doesn't apply; use Granville's generalisation or CRT over prime factors
You need an **exact** (non-modular) binomial → big integers / Pascal, no Lucas
n is small enough to build a Pascal triangle mod p → just do that

Interview takeaway

Lucas' theorem says a binomial coefficient modulo a prime is the product of the binomials of the base-p digits. It's the tool for nCr mod p exactly when the factorial method dies — n bigger than p. Precompute factorials and inverses up to p−1 once, peel off base-p digits of n and r together, multiply the per-digit C(nᵢ, rᵢ), and short-circuit to 0 the moment a digit has rᵢ > nᵢ. Pair it with CRT to handle composite moduli.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternLucas' theorem — nCr modulo a small prime when n exceeds p. Recognise it whenever the factorial method's p > n precondition fails. Decompose into base-p digit binomials, precompute factorials only up to p−1, and short-circuit on a zero digit. Pair with CRT for composite moduli; it's the large-n counterpart of nCr mod p.

Practice queueDirect variations and pattern siblings

Direct follow-ups

nCr mod p
The p > n companion — factorials + Fermat; Lucas reuses the same per-digit binomial.
Chinese Remainder Theorem
Combine Lucas results modulo several primes to get nCr modulo a composite.
Modular Exponentiation
The Fermat inverse fact[p−1]^(p−2) used to seed the inverse-factorial table is one modpow.
Kummer's Theorem
Coming soon
Counts the power of p dividing C(n, r) via base-p carries — the companion to Lucas mod p.

Same pattern

←

GCD of Two Numbers

Continue · Next problem

Matrix Exponentiation (Fibonacci)

hardMath GeometryRarely asked

Lucas' Theorem

Math & Number Theory · 25 of 36 · 12 min

Given integers n and r and a prime p, compute the binomial coefficient C(n, r) mod p.

In plain English

Examples

Example 1

Input: n = 10, r = 3, p = 3
Output: 0
Note: Base 3: 10 = (1 0 1)₃, 3 = (0 1 0)₃. Digit-wise: C(1,0)·C(0,1)·C(1,0). The middle factor C(0,1) = 0 → whole product 0. (Indeed C(10,3)=120, and 120 mod 3 = 0.)

Example 2

Input: n = 1000, r = 500, p = 13
Output: 0
Note: At least one base-13 digit of 500 exceeds the matching digit of 1000, making a factor 0 (C(1000,500) mod 13 = 0).

Example 3

Input: n = 5, r = 2, p = 13
Output: 10
Note: n, r < p so there's a single digit: C(5,2) = 10, and 10 mod 13 = 10. Lucas reduces to the ordinary binomial here.

Constraints

0 ≤ r ≤ n ≤ 10¹⁸ (n can vastly exceed p)
p is prime and 2 ≤ p ≤ 10⁶ or so (small enough to precompute factorials up to p−1)
Define C(n, r) = 0 when r > n
Use long in Java for digit products; Python big ints are exact

Clarifying questions4First question: Is n larger than p?Explore questions

Q1.Is n larger than p?
That's the whole reason for Lucas. If p > n I'd just use factorials + Fermat. When n ≥ p, those factorials hit a factor of p and the method collapses, so I switch to Lucas.
Q2.Is p prime?
Lucas requires a prime modulus. For a prime power I'd use Granville's generalisation; for a general composite I'd factor it, apply Lucas per prime power, and combine with CRT.
Q3.How small is p — can I precompute factorials up to p−1?
Yes, p is small (say ≤ 10⁶), so I build fact[0..p−1] and inverse-factorials once with Fermat, then each digit's binomial is O(1).
Q4.What if r > n?
C(n, r) = 0. Lucas also returns 0 whenever any base-p digit of r exceeds the corresponding digit of n — I short-circuit there.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Applying the factorial method with n ≥ p (division by a non-invertible factorial), forgetting that rᵢ > nᵢ in any digit makes the whole result 0, or using Lucas with a non-prime modulus.

How to stand out

Explain WHY n ≥ p breaks the factorial method, state Lucas as C(n,r) ≡ ∏ C(nᵢ,rᵢ) (mod p), note the 0 short-circuit, and mention CRT-over-primes for composite moduli.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Factorial + Fermat Inverse (Baseline — fails when n ≥ p)	`O(n) precompute, O(1) query (when valid)`	`O(n)`	Mention first to show you know the standard method AND precisely why it breaks once n ≥ p — that diagnosis motivates Lucas.	Read
2	Lucas' Theorem (Optimal)Optimal	`O(p + log_p(n)) — O(p) precompute, O(log_p n) digits per query`	`O(p)`	The answer they want when n can exceed a small prime p. Phrase it as 'write n and r in base p; the coefficient is the product of the digit binomials'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Factorial + Fermat Inverse (Baseline — fails when n ≥ p)

TimeO(n) precompute, O(1) query (when valid)SpaceO(n)

Mention first to show you know the standard method AND precisely why it breaks once n ≥ p — that diagnosis motivates Lucas.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The standard nCr mod p uses fact[n]·invFact[r]·invFact[n−r] with Fermat inverses. What two things go wrong when n is 10¹⁸ and p is small?

2Hint 2Explore hint

First, you can't allocate a factorial table of length 10¹⁸. Second — subtler — once n ≥ p, n! is divisible by p, so fact[n] ≡ 0 mod p and has NO inverse.

3Hint 3Explore hint

So the method is both infeasible and mathematically invalid here. You need a formula that works digit-by-digit in base p, keeping every factorial argument below p.

A · Core idea

Failure 1 — the table can't exist. With n up to 10¹⁸, a factorial array of length n+1 is impossible to allocate. There isn't enough memory in the universe for 10¹⁸ entries.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10, r = 3, p = 3

build fact

fact[3] = 6 ≡ 0 (mod 3)

Statealready a zero

Final resultmethod invalid for n ≥ p

C · Code with teaching comments

solution.javaJava

Factorial + Fermat Inverse (Baseline — fails when n ≥ p) — reference

1 teaching note

1
// Valid ONLY when p > n. Shown to expose the failure mode for n >= p.
2
public long nCrFactorial(int n, int r, long p, long[] fact, long[] invFact) {
3
    if (r < 0 || r > n) return 0;
4
    // If n >= p, fact[n] % p == 0 (no inverse) and the table can't even be built for huge n.
5
    // Correct only if p > n; when n ≥ p, fact[n] ≡ 0 mod p so invFact is bogus and this
6
    // is invalid.
7
    return fact[n] * invFact[r] % p * invFact[n - r] % p;
8
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.8 lines

D · Why it works and complexityO(n) precompute, O(1) query (when valid) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Using it when n ≥ p — fact[n] ≡ 0 mod p is not invertible.Explore edge cases

Pitfalls

Using it when n ≥ p — fact[n] ≡ 0 mod p is not invertible.
Trying to allocate a factorial table for n = 10¹⁸.
Assuming Fermat gives an inverse of 0 — it returns 0, not a real inverse.

03.2

Approach 2 of 2 · Optimal

Lucas' Theorem (Optimal)

TimeO(p + log_p(n)) — O(p) precompute, O(log_p n) digits per querySpaceO(p)

The answer they want when n can exceed a small prime p. Phrase it as 'write n and r in base p; the coefficient is the product of the digit binomials'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write n and r in base p. Lucas' theorem says C(n, r) ≡ ∏ C(nᵢ, rᵢ) (mod p) over the base-p digits. Each digit is < p — what does that buy you?

2Hint 2Explore hint

Precompute factorials and inverse-factorials only up to p−1 (one Fermat inverse + backward sweep). Then each digit's C(nᵢ, rᵢ) is O(1).

3Hint 3Explore hint

Peel digits with n % p and r % p, multiply the digit binomials, recurse on n / p and r / p. If any rᵢ > nᵢ the digit binomial is 0, so the whole answer is 0 — short-circuit.

A · Core idea

Lucas' theorem reduces a binomial coefficient modulo a prime to a product of much smaller binomials — the binomials of the base-p digits.

The statement. Write n and r in base p:

n = nₖ·pᵏ + … + n₁·p + n₀, r = rₖ·pᵏ + … + r₁·p + r₀, with each digit in [0, p). Then

C(n, r) ≡ C(nₖ, rₖ) · … · C(n₁, r₁) · C(n₀, r₀) (mod p).

Every factor C(nᵢ, rᵢ) has both arguments below p, so no factorial argument ever reaches p — the inverse problem that killed the baseline never arises.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10, r = 3, p = 3

Array state

digits

n=(1,0,1)₃, r=(0,1,0)₃ (low→high)

digit ↓

n0=1,r0=0

[0]

n1=0,r1=1

[1]

n2=1,r2=0

[2]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Lucas' Theorem (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
class Lucas {
4
    private final long p;
5
    private final long[] fact, invFact;
6
 
7
    Lucas(long p) {
8
        this.p = p;
9
        int sz = (int) p;
10
        fact = new long[sz];
11
        invFact = new long[sz];
12
        fact[0] = 1 % p;
13
        // Factorials only up to p−1 — O(p) setup, NOT O(n); this is what makes huge n
14
        // feasible.
15
        for (int i = 1; i < sz; i++) fact[i] = fact[i - 1] * i % p;
16
        // One Fermat inverse seeds the inverse-factorial table.
17
        invFact[sz - 1] = modpow(fact[sz - 1], p - 2, p);
18
        for (int i = sz - 2; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % p;
19
    }
20
 
21
    // C(ni, ri) mod p for digits below p.
22
    private long smallNcr(long n, long r) {
23
        if (r < 0 || r > n) return 0;
24
        return fact[(int) n] * invFact[(int) r] % p * invFact[(int) (n - r)] % p;
25
    }
26
 
27
    long nCr(long n, long r) {
28
        long result = 1 % p;
29
        while (r > 0 || n > 0) {
30
            // Lowest base-p digits of n and r.
31
            long ni = n % p, ri = r % p;
32
            if (ri > ni) return 0;           // digit binomial 0 -> whole answer 0
33
            // Multiply in this digit's binomial, reduced mod p so the long stays
34
            // bounded.
35
            result = result * smallNcr(ni, ri) % p;
36
            // Shift to the next base-p digit; loop runs O(log_p n) times.
37
            n /= p; r /= p;
38
        }
39
        return result;
40
    }
41
 
42
    private long modpow(long base, long exp, long mod) {
43
        long r = 1 % mod; base %= mod;
44
        while (exp > 0) {
45
            if ((exp & 1) == 1) r = r * base % mod;
46
            base = base * base % mod;
47
            exp >>= 1;
48
        }
49
        return r;
50
    }
51
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.51 lines

D · Why it works and complexityO(p + log_p(n)) — O(p) precompute, O(log_p n) digits per query timeO(p) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls9n < p and r < p — Single digit: Lucas reduces to the ordinary C(n, r) mod p.Explore edge cases

Edge cases handled

n < p and r < pSingle digit: Lucas reduces to the ordinary C(n, r) mod p.
r = 0All digits of r are 0, every C(nᵢ, 0) = 1 → result 1.
r > nSome digit has rᵢ > nᵢ (or higher r digits exceed n's) → 0.
p = 2Lucas in base 2 gives Kummer's parity: C(n,r) is odd iff r's bits are a subset of n's.

Pitfalls

Using Lucas with a non-prime modulus — it only holds mod a prime; use Granville + CRT otherwise.
Forgetting the rᵢ > nᵢ short-circuit — must contribute a 0 factor.
Precomputing factorials up to n instead of p−1 — defeats the purpose for huge n.
Stopping the loop too early — continue while either n or r still has digits.
Letting digit products overflow in Java — reduce mod p after each multiply, use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class Lucas { private final long p; private final long[] fact, invFact;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class Lucas {
    private final long p;
    private final long[] fact, invFact;

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Factorial method with n ≥ p

Explore the code comparison

Don't write this

# n = 10, p = 3:
return fact[n] * inv_fact[r] % p * inv_fact[n - r] % p  # fact[10] % 3 == 0

Write this instead

lucas = Lucas(p)
return lucas.n_cr(n, r)   # digit-wise binomials, every argument < p

Missing the zero-digit short-circuit

If any base-p digit of r exceeds the matching digit of n, C(nᵢ, rᵢ) = 0 and the full product must be 0. Skipping that check (e.g. clamping) gives a wrong nonzero answer.

Explore the code comparison

Don't write this

long ni = n % p, ri = r % p;
result = result * smallNcr(ni, ri) % p; // smallNcr must return 0 when ri>ni

Write this instead

long ni = n % p, ri = r % p;
if (ri > ni) return 0;                  // explicit short-circuit
result = result * smallNcr(ni, ri) % p;

Lucas on a composite modulus

Lucas' theorem holds modulo a prime (its proof uses (1+x)^p ≡ 1+x^p mod p). For a composite m, factor m into prime powers, apply Lucas/Granville per factor, then CRT-combine.

Explore the code comparison

Don't write this

lucas = Lucas(12)        # 12 is not prime — invalid

Write this instead

# factor 12 = 4 * 3; compute C(n,r) mod 4 (Granville) and mod 3 (Lucas),
# then combine with CRT to get C(n,r) mod 12

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reduce a huge nCr mod a small prime to a product of digit-wise binomials in base p

Code pattern to memorize

write n = (n_k ... n_1 n_0) and r = (r_k ... r_1 r_0) in base p
C(n, r) mod p = product over i of C(n_i, r_i) mod p
if any r_i > n_i: the product (and the answer) is 0
each C(n_i, r_i) with n_i, r_i < p via factorials + Fermat inverse

Rules to remember

1Use Lucas when n can exceed p (p small). The plain factorial method needs p > n; Lucas removes that limit.
2Process n and r digit by digit in base p (repeatedly take % p then /= p). The recursion bottoms out when both reach 0.
3If at any digit rᵢ > nᵢ, then C(nᵢ, rᵢ) = 0, which forces the whole product to 0 — short-circuit and return 0.
4Each per-digit C(nᵢ, rᵢ) has nᵢ, rᵢ < p, so precompute factorials and inverse-factorials up to p−1 once (Fermat inverse) and answer each digit in O(1).
5The modulus must be prime (Lucas is a statement mod a prime). For prime powers use the generalised Granville/Andrew theorem; combine several primes with CRT. Use long in Java for digit products.

Use this pattern when

Compute `C(n, r) mod p` where `n` is astronomically large (up to 10¹⁸) and `p` is a **small prime**
Counting problems mod a small prime where n far exceeds the modulus
Combined with CRT to get nCr modulo a composite by working over its prime factors
Anywhere the plain factorial-inverse method fails because `p ≤ n`

Choose another pattern when

`p > n` (e.g. p = 1e9+7 and n ≤ 1e6) → the plain factorial + Fermat method is simpler and direct
The modulus is **not prime** → Lucas doesn't apply; use Granville's generalisation or CRT over prime factors
You need an **exact** (non-modular) binomial → big integers / Pascal, no Lucas
n is small enough to build a Pascal triangle mod p → just do that

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

nCr mod p
The p > n companion — factorials + Fermat; Lucas reuses the same per-digit binomial.
Chinese Remainder Theorem
Combine Lucas results modulo several primes to get nCr modulo a composite.
Modular Exponentiation
The Fermat inverse fact[p−1]^(p−2) used to seed the inverse-factorial table is one modpow.
Kummer's Theorem
Coming soon
Counts the power of p dividing C(n, r) via base-p carries — the companion to Lucas mod p.

Same pattern

←

GCD of Two Numbers

Continue · Next problem

Matrix Exponentiation (Fibonacci)