Lucas's theorem

Statement

Let $p$ be a prime number, and let $m$ and $n$ be natural numbers with base-$p$ digits $m = \sum_{i=0}^{k} m_i p^i$ and $n = \sum_{i=0}^{k} n_i p^i$, where $0 \le m_i, n_i < p$. Then $$\binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \pmod p,$$ with the convention $\binom{a}{b} = 0$ when $b > a$.

Remarks

A consequence: $p \mid \binom{m}{n}$ if and only if $n_i > m_i$ for some digit $i$. For example, with $p = 3$: $10 = 101_3$ and $4 = 011_3$. The theorem gives $\binom{10}{4} \equiv \binom{1}{0} \binom{0}{1} \binom{1}{1} = 0 \pmod 3$, and indeed $\binom{10}{4} = 210$. For $p = 2$, the binomial coefficient $\binom{m}{n}$ is odd if and only if $m$ has a binary digit $1$ at each place where $n$ has one.

History

Édouard Lucas published the theorem in 1878.

Explanations

L1 human

To find a binomial coefficient modulo a prime $p$, write both numbers in base $p$. Then compute small binomial coefficients digit by digit and multiply them. This explains the pattern of odd numbers in Pascal's triangle, which looks like the Sierpiński triangle.