Lucas' theorem

Statement

Suppose $a$ and $b$ are nonnegative integers and $p$ is a prime number. Suppose $a=a_{0}+a_{1}p+a_{2}p^{2}+\dots +a_{r}p^{r}$ and $b=b_{0}+b_{1}p+b_{2}p^{2}+\dots +b_{s}p^{s}$ are the expressions of $a$ and $b$ in base $p$, so that each $a_{i},b_{j}$ is in the set $\{0,1,2,\dots ,p-1\}$. if $r<s$, define $a_{i}=0$ for $r<i\leq s$. Then, we have:

${\binom {a}{b}}\equiv \prod _{i=0}^{s}{\binom {a_{i}}{b_{i}}}{\pmod {p}}$

By convention, ${\binom {x}{y}}=0$ if $x=0$ or if $y>x$.

In particular, we have the following: If $a$ is a power of $p$ and $b<a$, then ${\binom {a}{b}}$ is relatively prime to $p$. For more on this special case and alternative proofs of it, see Lucas' theorem prime power case.