Sign in to watch this lesson
Advanced - Combinatorics, Games and Puzzles Ā· 5:08
Binomials Modulo Anything
The textbook n! / (k! (n - k)!) with a modular inverse only works modulo a large prime. For a small prime, Lucas's theorem multiplies the binomials of the base-p digit pairs, which for p = 2 turns into a bit test and draws the Sierpinski triangle; for a prime power we strip the prime out of every factorial and track its exponent; and any other modulus is split into prime powers and recombined with the Chinese remainder theorem.
You will learn
- Explain why n! / (k! (n - k)!) with modular inverses fails for a small prime p <= n and for a composite modulus
- Compute C(n, k) mod a prime p with Lucas's theorem by multiplying the binomials of the base-p digit pairs, and use its p = 2 form: C(n, k) is odd iff (k & n) == k
- Compute C(n, k) mod p^e by writing x! = p^c(x) g(x), dividing the parts coprime to p with inverses and returning 0 when c(n) - c(k) - c(n - k) >= e
- Combine answers modulo the prime powers of any m with the Chinese remainder theorem