Lucas' Theorem — C(n,k) mod p via Base-p Digits

Write n and k in base p, multiply the small per-digit binomials C(n_i, k_i) mod p, and short-circuit to 0 the instant a digit k_i > n_i.

Setup O(p) Query O(log_p n) Space O(p)
step 0

Base-p digits of n and k

running product (mod p): 1
current digit k_i ≤ n_i (factor ≥ 1) k_i > n_i ⇒ 0

State

prime p3
n (base p)111
k (base p)011
digit position i—
factor C(n_i,k_i)—
product mod p1
C(n,k) mod p—
true C(n,k) mod p—

Complexity

stepcost
build fact/invFact (size p)O(p)
one small binomial C(a,b)O(1)
digit decompositionO(log_p n)
full query C(n,k) mod pO(p + log_p n)
plain factorial methodO(n)
Press Step to peel one base-p digit at a time, or Run to play the whole computation.

Lucas' theorem: for prime p, C(n,k) ≡ ∏_i C(n_i, k_i) (mod p) over the base-p digits. A single factor of 0 (when k_i > n_i) makes the whole product 0. Each small C(n_i, k_i) comes from a precomputed factorial table of size p.