Lesson 9

Lucas's theorem immediately tells us when a binomial coefficient is not divisible by \(p\). Indeed, \[\binom{n}{k}\not\equiv 0\pmod p\] if and only if \[k_{i}\le n_{i}\] for every base-\(p\) digit.

The reason is that if \(k_{i}>n_{i}\), then one of the factors in Lucas's product is zero. Conversely, if \(k_{i}\le n_{i}\) for all \(i\), then each small coefficient \(\binom{n_i}{k_i}\) is nonzero modulo \(p\), since all numbers involved are smaller than \(p\).