Intuition, Vocabulary and Foundations
A modular combinatorics calculator should behave like a route planner, not like one formula with % modulus appended. For example, $\binom{10}{3}=120$, so the answer modulo $7$ is $1$ and modulo $12$ is $0$. The integer quantity is the same, but the efficient and valid modular computation differs because every nonzero residue modulo a prime is invertible, whereas factorial factors such as $3$ and $4$ are not invertible modulo $12$.
Factorials count orderings, permutations count ordered selections, and combinations count unordered selections:
$$ n!=1\cdot2\cdots n,\qquad P(n,k)=\frac{n!}{(n-k)!},\qquad \binom nk=\frac{n!}{k!(n-k)!}. $$
These quotients are exact over the integers, but modular division is valid only when the denominator has an inverse. For a prime power $p^q$, separate each factorial into its $p$-adic exponent and its unit part. Compute the unit quotient using modular inverses, restore the remaining power of $p$, and combine answers for distinct prime powers with the Chinese Remainder Theorem.
Catalan-style formulas illustrate why the expression matters. Although $C_n=\binom{2n}{n}/(n+1)$, division by $n+1$ may be invalid modulo a composite number. The equivalent identity $C_n=\binom{2n}{n}-\binom{2n}{n+1}$ uses no modular division and remains valid for every positive modulus.
First define the combinatorial quantity over the integers; only then choose a modular algorithm whose inverses are guaranteed to exist. A certificate should record the modulus factorization, selected method, domain bounds, and residues used in reconstruction.
| Concept | Concrete example | Non-example or boundary | Assumption and question answered |
|---|---|---|---|
| Factorial | $5!=120$ | Negative factorial input | For $n\ge0$, how many orders contain all $n$ distinct objects? |
| Permutation | $P(5,2)=5\cdot4=20$ | $P(3,5)$, because more objects are selected than exist | For $0\le k\le n$, how many ordered selections are possible? |
| Combination | $\binom{5}{2}=10$ | Replacing exact division by an unavailable modular inverse | For $0\le k\le n$, how many unordered selections are possible? |
| Prime factorial method | $\binom{6}{2}\equiv1\pmod7$ | Using a factorial inverse when $n\ge p$, so $n!\equiv0\pmod p$ | Requires prime $p$ and typically $n\lt p$ |
| Lucas theorem | $\binom{10}{3}\equiv1\pmod7$ from base-$7$ digits | Applying Lucas directly to a composite modulus | Requires a prime modulus and reduces the query digit by digit |
| $p$-adic valuation | $v_2(10!)=5+2+1=8$ | Treating factors of $p$ as invertible modulo $p^q$ | How many copies of $p$ survive in a factorial quotient? |
| Prime-power residue | Compute separately modulo $8$ and modulo $9$ | Assuming a field modulo $8$ | Unit factorials are invertible after all $p$-factors are removed |
| CRT reconstruction | Residues modulo $8$ and $9$ determine one residue modulo $72$ | Combining moduli that were not separated into coprime factors | Distinct prime powers are pairwise coprime |
| Catalan identity | $C_3=\binom63-\binom64=5$ | Dividing by $4$ modulo $8$ | Use a division-free identity when invertibility is uncertain |
Step-by-Step Derivations and Algorithms
For a prime modulus $p$ with $n\lt p$, precompute factorials and inverse factorials. Fermat's theorem gives $x^{-1}\equiv x^{p-2}\pmod p$ for nonzero $x$, so
$$ \binom nk\equiv n!\,(k!)^{-1}\,((n-k)!)^{-1}\pmod p. $$
One table build costs $O(p)$ or $O(N)$ up to the largest supported $n$, and each query then costs $O(1)$.
When $n\ge p$, write $n=\sum n_i p^i$ and $k=\sum k_i p^i$. Lucas theorem states
$$ \binom nk\equiv\prod_i\binom{n_i}{k_i}\pmod p. $$
Each digit lies below $p$, so the factorial method applies locally. If any $k_i>n_i$, the corresponding digit combination is zero and therefore the entire result is zero.
For a prime power $M=p^q$, Legendre's formula computes
$$ v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor. $$
Let $g(n)$ be the factorial product with all factors of $p$ removed, evaluated modulo $M$. Then
$$ \binom nk\equiv g(n)\,g(k)^{-1}\,g(n-k)^{-1}\, p^{\,v_p(n!)-v_p(k!)-v_p((n-k)!)} \pmod M. $$
If the remaining exponent is at least $q$, the residue is zero. Otherwise, all three unit factorials are coprime to $M$, so their inverses exist. Finally, factor a composite modulus into pairwise coprime prime powers, compute one residue for each, and reconstruct the unique result modulo their product with CRT.
flowchart TD
A[Validate query and modulus] --> B[Factor the modulus]
B --> C{Factorization shape}
C -->|Prime and n below p| D[Cached factorial tables]
C -->|Prime and large n| E[Lucas digit decomposition]
C -->|Prime power| F[Valuation plus unit factorial]
C -->|Several prime powers| G[Evaluate every component]
G --> H[CRT reconstruction]
D --> I[Return residue and certificate]
E --> I
F --> I
H --> I
Correctness follows from preserving the exact factorial quotient while separating nonunits from invertible unit factors. With a precomputed table of size $p^q$, a prime-power query uses $O(\log_p n)$ arithmetic steps and $O(p^q)$ cached space; Lucas uses $O(\log_p n)$ digit queries, and CRT adds logarithmic extended-gcd work per component.
Implementation, Complexity and Engineering
A calculator must state its scale policy. The reference implementation precomputes unit-factorial tables only when a prime power does not exceed table_limit; it rejects a larger table rather than risking an unexpected allocation. Tables are cached by prime power and reused across queries. The result includes a certificate naming the selected route, modulus factorization, component residues, and verification result.
The API defines out-of-range combinations and permutations as zero, accepts modulus $1$ with the unique residue zero, and rejects negative dimensions or nonpositive moduli. Catalan numbers use a subtraction identity instead of modular division. Python's unbounded integers avoid overflow in CRT products; fixed-width ports need checked multiplication or a wider intermediate type.
| Method | Preconditions and complexity | Suitable workload | Failure mode and mitigation |
|---|---|---|---|
| Direct integer calculation | Exact arithmetic; cost grows with $n$ and integer size | Small inputs and testing oracle | Large intermediate integers; use only below an explicit scale limit |
| Prime factorial tables | Prime $p$, normally $n\lt p$; $O(p)$ build and $O(1)$ query | Many queries under one moderate prime | Factorial becomes zero when $n\ge p$; route such queries to Lucas |
| Lucas theorem | Prime $p$; $O(p)$ table and $O(\log_p n)$ digit work | Huge $n$ with manageable $p$ | Table infeasible for a very large prime; reject or choose another method |
| Prime-power unit factorial | Modulus $p^q$; $O(p^q)$ table and $O(\log_p n)$ query | Repeated queries for manageable prime powers | Inverting factors containing $p$; remove them and track their valuation |
| CRT reconstruction | Pairwise-coprime prime-power components | General composite modulus | Product overflow in fixed-width code; use widened or checked arithmetic |
| Direct permutation product | $0\le k\le n$; $O(k)$ time and $O(1)$ space | Occasional permutation queries | Slow for very large $k$; add factorial or prime-power routing if needed |
| Division-free Catalan | Two binomial queries; valid for every modulus | Composite moduli and uniform APIs | Using $(n+1)^{-1}$ when it does not exist; prefer subtraction identity |
| Cached tables | Reuses work by prime or prime power | High query volume with repeated moduli | Unbounded cache memory; impose a byte or entry budget and expose metrics |
Applications, Case Studies and Exercises
An approachable calculator might answer classroom queries such as $\binom{100}{40}\bmod72$. It factors $72=2^3\cdot3^2$, evaluates the binomial modulo $8$ and $9$, reconstructs the answer with CRT, and reports a certificate containing both component residues. This makes the result inspectable rather than merely numerical.
A professionally realistic service receives heterogeneous moduli and very large indices. It must group requests by modulus, reuse tables, reject infeasible prime powers before allocation, and expose the chosen algorithm in logs or responses. Workload measurements should determine cache size and preprocessing thresholds. Correctness certificates can be sampled by recomputing small cases exactly and always checking reconstructed values against every prime-power residue.
Exercises should progress from explaining when factorial division is valid, through deriving the valuation formula and Lucas decomposition, to implementing multinomial coefficients. Debugging tasks can target forgotten zero residues, $k>n$, modulus $1$, incorrect CRT normalization, and tables that exceed policy. Extension tasks can add bounded cache eviction, batch grouping, and an independent exact-arithmetic verification mode.
Apply Modular Combinatorics Calculator
Case study 1 — inspect one composite query. Evaluate $\binom{100}{40}\bmod72$. Checkpoint 1: factor $72$ into $8$ and $9$. Checkpoint 2: record the residue produced for each prime power. Checkpoint 3: reconstruct one value in [0, 72) and verify it against comb(100, 40) % 72. Success requires a certificate whose factorization multiplies to $72$ and whose CRT value matches both component residues.
Case study 2 — mixed production batch. Create 10,000 deterministic queries drawn from repeated prime moduli, small prime powers, and composite products, with some $n$ values above their prime modulus. Record the selected method, cache hits, table bytes, preprocessing time, median query time, and rejection count. Cross-check every query with $n\le500$ using exact arithmetic. Success requires zero mismatches, no allocation above the configured limit, and an explicit reason for every rejected query.
Hands-on deliverable. Implement CLI commands for choose, permute, and catalan, returning JSON with value, modulus, method, factors, component_residues, and verified. Add boundary tests for $k=0$, $k=n$, $k>n$, modulus $1$, a prime with $n\ge p$, a zero residue modulo a prime power, and an unsupported table size. The calculator is complete when its documentation states every domain restriction and at least 5,000 randomized small cases match exact arithmetic.
Select factorial tables only when their inverses exist, Lucas only for prime moduli, and unit-factorial plus CRT methods for prime powers and composites. The recurring misconceptions are that exact integer division permits modular division, that every prime-sized table is affordable, and that a residue without its domain assumptions is a sufficient result; the prerequisite composite-binomial machinery supplies the proof obligations for each route.