Binomial Coefficient Modulo Calculator
Compute combinations modulo any practical integer with efficient methods, prime checks, large-number Lucas support, clear steps, examples, history, and export tools included for students.
Calculator
Formula used
The ordinary binomial coefficient is C(n,k) = n! / (k!(n-k)!).
Then the calculator reduces that integer modulo m.
Prime moduli also permit modular inverses and Lucas theorem.
How to use this calculator
- Enter nonnegative integers for n and k.
- Enter a positive modulus m.
- Keep Auto mode unless you need a specific method.
- Use Lucas mode for huge values with prime modulus.
- Review the result and calculation steps above.
- Export the result with CSV or PDF buttons.
Understanding binomial coefficients modulo m
A binomial coefficient counts selections without considering order. The expression C(n,k) counts ways to choose k objects. Modular arithmetic keeps only the remainder after division. Combining both ideas is common in combinatorics and algorithms. Direct factorials work well for very small inputs. They become impractical when factorial values grow beyond integer limits. This calculator therefore offers several safer computational methods.
The prime-factor method computes exponents inside the exact coefficient. It never divides modulo m, which helps composite moduli. Pascal recurrence builds coefficients from neighboring values. Reducing every addition modulo m controls number growth. Modular inverse mode is useful when the modulus is prime. Fermat's little theorem supplies the denominator inverse safely. However, direct modular division fails when an inverse does not exist.
Large values and Lucas theorem
Lucas theorem handles extremely large decimal n and k. It requires the modulus to be prime. The method writes both numbers using base-p digits. Each digit pair creates a smaller binomial coefficient. Their residues are multiplied modulo the same prime. This avoids constructing the enormous original coefficient.
Choosing a method
Auto mode prefers prime-factor computation for practical integer n. It switches to Lucas theorem for huge n with prime modulus. Direct mode is mainly educational and intentionally limited. Pascal mode is useful for recurrence demonstrations. Modular inverse mode shows prime-modulus division explicitly. For composite m, the prime-factor method is usually safer.
Always check whether k exceeds n before interpreting results. In that case, the standard coefficient is zero. The identity C(n,k)=C(n,n-k) also reduces work. The calculator applies this symmetry where appropriate. Exported reports preserve inputs, methods, and final residues. A saved history also helps compare repeated problems, confirm methods, and revisit examples without entering every value again. These records can support homework, testing, and reproducible computations.
Example table
| n | k | m | C(n,k) | Residue | Suggested method |
|---|---|---|---|---|---|
| 10 | 3 | 7 | 120 | 1 | Auto |
| 8 | 2 | 5 | 28 | 3 | Modular inverse |
| 20 | 10 | 12 | 184756 | 4 | Prime-factor |
| 100 | 25 | 13 | Large | 0 | Lucas theorem |
| 50 | 0 | 9 | 1 | 1 | Any |
Recent calculation history
FAQ
What does C(n,k) mod m mean?
It means calculate the binomial coefficient, then keep its remainder modulo m.
Why can modular division fail?
A denominator needs a multiplicative inverse modulo m. That inverse may not exist.
When should I use Lucas theorem?
Use it for very large n or k when the modulus is prime.
Does the calculator support composite moduli?
Yes. The prime-factor exact method works well for n up to 200,000.
What happens when k is greater than n?
The calculator returns zero under the standard combinatorial convention.
Why is direct factorial mode limited?
Factorials overflow machine integers quickly. Safer modular methods scale much better.
Use verified integer inputs and review the shown method.