When indices exceed the prime
The factorial method for binomial coefficients fails when the indices reach or exceed the prime modulus, since the needed inverses no longer exist. Lucas' theorem solves this by breaking the indices into digits in base the prime.
The digit product
Write both the top and bottom indices in the prime's base. Lucas' theorem says the whole coefficient under the prime equals the product of small binomial coefficients, one per digit position:
- Pair the digit of the top index with the digit of the bottom index at each position.
- Compute each small binomial of these single digits, which are below the prime.
- Multiply all the small coefficients under the prime.
If any bottom digit exceeds its matching top digit, that small coefficient is zero, making the whole result zero.
Why it helps
The small per digit binomials use indices below the prime, so the ordinary factorial and inverse method applies to each one safely, and only a handful of digits appear for a small prime.
Key idea
Lucas' theorem evaluates a binomial coefficient under a small prime by writing the indices in that base and multiplying the per digit small binomials, handling indices far larger than the prime itself.