Agnes Scott College
Larry Riddle, Agnes Scott College
image

Proof of Lucas's Theorem

Lucas's
Theorem

Let p be a prime number, and let r and c be written in p-ary notation

$$\begin{array}{l} r = {r_k} \cdots {r_2}{r_1}{r_0} = {r_0} + {r_1}p + {r_2}{p^2} + \cdots + {r_k}{p^k} \qquad (0 \le {r_i} \lt p) \\ c = {c_k} \cdots {c_2}{c_1}{c_0} = {c_0} + {c_1}p + {c_2}{p^2} + \cdots + {c_k}{p^k} \qquad (0 \le {c_i} \lt p) \\ \end{array}$$

Then

$$\left( {\begin{array}{*{20}{c}} r \\ c \\ \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{r_0}} \\ {{c_0}} \\ \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{r_1}} \\ {{c_1}} \\ \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{r_1}} \\ {{c_1}} \\ \end{array}} \right) \cdots \left( {\begin{array}{*{20}{c}} {{r_k}} \\ {{c_k}} \\ \end{array}} \right)(\bmod p)$$

We take here the standard convention that the binomial coefficient (r,c)=0 if c > r.

Lemma

We first need to show that \( (1 + x)^{p^{\Large{n}}} = 1 + x^{p^{\Large{n}}} \bmod p \) when p is a prime and n > 0. If 0 < k < pn, then

$$ \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = \frac{{p^n !}}{{k!(p^n - k)!}} = \frac{{p^n }}{k}\left( {\begin{array}{*{20}c} {p^n - 1} \\ {k - 1} \\ \end{array}} \right) $$

In particular, this means that \( k\left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = p^n \left( {\begin{array}{*{20}c} {p^n - 1} \\ {k - 1} \\ \end{array}} \right). \) At least n powers of p divide the right hand side of this equation, but at most n−1 powers of p divide k on the left side. Thus p must divide \( \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) \) and so \( \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = 0\bmod p. \) But when k = 0 or k = pn, then \( \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = 1. \)

These observations show that in the binomial theorem expansion of \( (1 + x)^{p^n }, \) only the first (k = 0) and last (k = pn) coefficients are non-zero mod p, and our desired result follows.

An Example

Suppose p = 5, r = 482, and c = 176. First note that

\[ \begin{array}{l} 482 = 3 \cdot 5^3 + 4 \cdot 5^2 + 1 \cdot 5 + 2 = 3412{\text{ (base }}5) \\ 176 = 1 \cdot 5^3 + 2 \cdot 5^2 + 0 \cdot 5 + 1 = 1201{\text{ (base }}5) \\ \end{array} \]

Then using the lemma allows us to write

\[ \begin{align} (1 + x)^{482} &= (1 + x)^{3(125)} \cdot (1 + x)^{4(25)} \cdot (1 + x)^{1(5)} \cdot (1 + x)^2 \\ &= (1 + x^{125} )^3 \cdot (1 + x^{25} )^4 \cdot (1 + x^5 )^1 \cdot (1 + x)^2 \bmod 5\\ \end{align} \]

On the left side, the coefficient of x176 will be \( \left( {\begin{array}{*{20}c} {482} \\ {176} \\ \end{array}} \right). \) The only way to get x176 in the product on the right side is to use one x125 term, two x25 terms, no x5 terms, and one x1 term. From the choices available in the product expansion above, we can do this in exactly \( \left( {\begin{array}{*{20}c} 3 \\ 1 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 4 \\ 2 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 1 \\ 0 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 2 \\ 1 \\ \end{array}} \right) \) ways. Hence

\[ \left( {\begin{array}{*{20}c} {482} \\ {176} \\ \end{array}} \right) = \left( {\begin{array}{*{20}c} 3 \\ 1 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 4 \\ 2 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 1 \\ 0 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 2 \\ 1 \\ \end{array}} \right)\bmod 5 \]

Proof

The proof is based on the Binomial Theorem for the expansion of (1+x)r as illustrated in the example above.

$$ \begin{align} \sum\limits_{c = 0}^r {\,\left( {\begin{array}{*{20}c} r \\ c \\ \end{array}} \right)\,x^c } &= \left( {{\kern 1pt} {\kern 1pt} 1 + x} \right)^{{\kern 1pt} r} = \prod\limits_{m = 0}^k {\,\left[ {\left( {{\kern 1pt} {\kern 1pt} 1 + x} \right)^{p^{\Large{m}} } } \right]^{ r_{ {\Large{m}}} } } \\ \\ &= \prod\limits_{m = 0}^k {\,\left( {1 + x^{{\kern 1pt} p^{ {\Large{m}}} } } \right)^{ r_{ {\Large{m}}} } (\bmod p)} \quad \left[ {{\text{since }}\left( {{\kern 1pt} {\kern 1pt} 1 + x} \right)^{p^{\Large{m}} } \equiv 1 + x^{{\kern 1pt} p^{\Large{m}} } (\bmod p)} \right] \\ \\ &= \prod\limits_{m = 0}^k {\,\left[ {\sum\limits_{s_{\Large{m}} = 0}^{r_{ {\Large{m}}} } {\left( {\begin{array}{*{20}c} {r_{ m} } \\ {s_{ m} } \\ \end{array}} \right)x^{{\kern 1pt} s_{\Large{m}} {\kern 1pt} p^{\Large{m}} } } } \right]} \,\,(\bmod p) \\ \\ &= \sum\limits_{c = 0}^r {\,\left[ {\sum {\prod\limits_{m = 0}^k {\left( {\begin{array}{*{20}c} {r_{ m} } \\ {s_{ m} } \\ \end{array}} \right)} } } \right]\,x^c } \;(\bmod p) \\ \end{align} $$

where for each value of c, the inner sum in the last sum is taken over all sets (s0, s1, s2, ..., sk) such that

\[ 0 \le s_m \le c_m \lt p \text{ and } \sum\limits_{m = 0}^k {s_m p^m = c} \]

But there is at most one such set of coefficients, given by sm = cm if every cm ≤ rm (since there is a unique representation for the p-ary form of c). If cm > rm for some m, then the inner sum is zero. In either case, the theorem follows by equating coefficients of xc for each 0 ≤ c ≤ r.

References

  1. Fine, N.J. "Binomial coefficients modulo a prime," Mathematical Association of America Monthly, December 1947 (Vol. 54, No. 10), 589-592. [Available at JSTOR]
  2. Su, Francis E., et al. "Lucas' Theorem," Math Fun Facts, http://www.math.hmc.edu/funfacts.