# Lucas' Theorem II

Elsewhere we established the following property of the binomial coefficients:

For $p$ prime, integers $a\ge 1$ and $0\lt k\lt p$,

$\displaystyle {p^{a} \choose k} \equiv 0 \space(\mbox{mod } p).$

This served to derive another useful identity

$\displaystyle (a + b)^p \equiv a^{p}+b^{p} \space(\mbox{mod } p).$

Which in turn is used to prove a theorem due to Édouard Lucas.

Let $n,m\in\mathbb{N}$ and let $p$ be a prime. Then

$\displaystyle {n \choose m} \equiv {\lfloor n/p \rfloor \choose \lfloor m/p \rfloor} {n\space\mbox{mod } p \choose m\space\mbox{mod } p} \space(\mbox{mod } p).$

The theorem can be stated in less formal terms:

Let $s,t\in\mathbb{N}$ and let $p$ be a prime. With $0\le q,r\lt p$,

$\displaystyle {sp+q \choose tp+r} \equiv {s \choose t} {q \choose r} \space(\mbox{mod } p).$

It is worth noting an immediate consequence of Lucas' theorem:

Let $n,m\in\mathbb{N}$ and $p$ a prime. Let $q,r$ be the remainders of division by $p$ of $n$ and $m$, respectively. Then $q\lt r$ implies

$\displaystyle {n \choose m}\equiv 0 \space(\mbox{mod } p),$

because $\displaystyle {q \choose r}=0$, for $q\lt r$. (For, in this case, there is no way to choose $r$ elements out of $q$.) This generalizes the aforementioned property $\displaystyle {p^{a} \choose k} \equiv 0 \space(\mbox{mod } p)$ of the binomial coefficients, and supplies another example of a more general statement being a consequence of a less general one.

### Proof of Lucas' theorem

Let $n=sp+q$, $m=tp+r$,$0\le q,r\lt p$. Then

\displaystyle \begin{align} (x+1)^{sp+q} &= (x+1)^{sp}\cdot (x+1)^{q} \\ &\equiv (x^{p}+1)^{s}\cdot (x+1)^{q} \space(\mbox{mod } p) \end{align}

But then

\displaystyle \begin{align} (x^{p}+1)^{s}\cdot (x+1)^{q} &= \sum_{i=0}^{s}{s\choose i}x^{ip}\cdot\sum_{j=0}^{q}{q \choose j}x^{j} \\ &= \sum_{j=0}^{q}{s\choose i}{q\choose j}x^{ip+j}. \end{align}

Now, in the last double sum every power of x appears just once, implying, in particular, that the coefficients by $x^{tp+r}$ on both sides of the equality are the same:

$\displaystyle {sp+q \choose tp+r}\equiv {s\choose t}{q\choose r},$

as required.

As an example,

$\displaystyle {31557 \choose 983} \equiv {2868 \choose 89}{9 \choose 4} \space(\mbox{mod } 11).$

To compute $\displaystyle{2868 \choose 89}$ we can apply the the theorem again, and so on - if necessary:

$\displaystyle {31557 \choose 983} \equiv {2868 \choose 89}{9 \choose 4} \equiv {260 \choose 8}{8 \choose 1}{9 \choose 4} \equiv {23 \choose 0}{7 \choose 8}{8 \choose 1}{9 \choose 4} \space(\mbox{mod } 11).$

And this is immediately $0$ due to the presence of the term $\displaystyle {7 \choose 8}$.

Thus Lucas' theorem, when applied repeatedly, can greatly simplify computing binomial coefficients modulo a prime. This successive of the two numbers $n$ and $m$ by $p$ is nothing but an algorithm for finding their expansions in base $p$. For example,

\begin{align} 31557 &= ((23\cdot 11 + 7)11+ 8)11+ 9 \\ &=(((2\cdot 11 + 1)11+ 7)11+ 8)11+ 9 \\ &= (21789)_{11}. \end{align}

$983 = ((8\cdot 11 + 1)11+ 4 = (814)_{11}.$

Padding on the left, the example can be rewritten as

$\displaystyle {31557 \choose 983} \equiv {2 \choose 0}{1 \choose 0}{7 \choose 8}{8 \choose 1}{9 \choose 4} \space(\mbox{mod } 11).$

In general, we have the following

### Corollary

Let $n,m\in\mathbb{N}$ and $p$ a prime. Assume in base $p$, $n=(n_{v}n_{v-1}\ldots n_{1}n_{0})_{p}$ and $m=(m_{v}m_{v-1}\ldots m_{1}m_{0})_{p}$, where one of the numbers may need to be padded with $0$s on the left. Then

$\displaystyle {n \choose m} \equiv {n_{v} \choose m_{v}}{n_{v-1} \choose m_{v-1}}\ldots {n_{1} \choose m_{1}}{n_{0} \choose m_{0}} \space(\mbox{mod } p).$

To expand on what we have already observed, if for some $i$, $0\le i\le v$, $n_{i}\lt m_{i}$, then $\displaystyle{n \choose m}\equiv 0\space(\mbox{mod } p)$. In the binary case, i.e. when $p=2$, this means that $\displaystyle{n \choose m}$ is even whenever $(n)_{2}$ has digit $0$ in one of the positions where $(m)_{2}$ has $1$. Compare this with what we found previously.

### References

1. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
2. D. Fuchs, S. Tabachnikov, Mathematical Omnibus: Thirty Lectures on Classic Mathematics , AMS, 2007
3. V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012
4. I. Stewart, Game, Set and Math, Penguin Books, 1989
5. S. Tabachnikov, Kvant Selecta: Algebra and Analysis, I, AMS, 1999