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

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

Pascal's Triangle and the Binomial Coefficients

71867862