Sign in to watch this lesson
Advanced - Number Theory · 4:21
Factorials mod p and Legendre's Formula
n! mod p is simply 0 once n ≥ p, yet binomials mod p need factorials, so we split n! into two parts: the number of factors p it contains, counted by Legendre's formula ν_p(n!) = Σ ⌊n/p^i⌋, and what is left modulo p after removing them. Wilson's theorem turns every full block of p − 1 numbers into −1, which gives n! mod p without the p's in O(log_p n) after an O(p) precomputation, and together the two parts give C(n, k) mod p for huge n.
You will learn
- Count the factors p in n! with Legendre's formula ν_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + …, and the trailing zeros of n! in any base b by factoring b
- Explain Wilson's theorem (p − 1)! ≡ −1 (mod p) by pairing each residue with its inverse
- Compute n! mod p with all factors p removed in O(p + log_p n) by splitting 1..n into blocks of p
- Compute C(n, k) mod a small prime p for n, k up to 10^18 by comparing Legendre counts and dividing stripped factorials