Lucas' Theorem

Lucas' theorem is a result about binomial coefficients modulo a prime $p$. It answers questions like:

• For which $m$ and $n$ is $\binom{m}{n}$ even?
• What is the remainder when a binomial coefficient like $\binom{100}{30}$ is divided by a prime number like $13$?
• How many entries in the $34^\text{th}$ row of Pascal's triangle are divisible by $11$? Which entries are not? What are they congruent to mod $11$?

Lucas' theorem states that for non-negative integers $m$ and $n$, and a prime $p$, $${m \choose n} \equiv \prod_{i=0}^{k} {m_{i} \choose n_{i}} \pmod p,$$ where $m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots+m_{1}p+m_{0}$ and $n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots+n_{1}p+n_{0}$ are the base $p$ expansions of $m$ and $n,$ respectively. This uses the convention that $m \choose n$=0 when $m<n$.

In particular, $\binom{m}{n}$ is divisible by $p$ if and only if at least one of the base-$p$ digits of $n$ is greater than the corresponding base-$p$ digit of $m$.

To look at a tangible example, take $p=2.$ Then $\binom{m}{n}$ is even if and only if at least one of the binary digits of $n$ is greater than the corresponding binary digits of $m.$ So, $\binom{8}{3} = 56$ is even because $3=0011_2$ has a greater digit than $8=1000_2$ (specifically, the rightmost digit).

Another interesting consequence is that $\binom{2^k-1}{m}$ is always odd, since $2^k-1$ is all 1s when written in binary; e.g., $\binom{31}{m}$ is always odd.

One of the most common problems to tackle is a direct application of Lucas' theorem: what is the remainder of a binomial coefficient when divided by a prime number?

Find the remainder when $\dbinom{1000}{300}$ is divided by 13.

---

We first write both 1000 and 300 in terms of the sum of powers of 13: $$1000 = 5 (13^2) + 11(13) + 12 \quad \text{ and }\quad 300 = 1(13^2)+ 10(13) + 1.$$ Then apply Lucas' theorem: $$\begin{aligned} \dbinom{1000}{300} \equiv \dbinom{5}{1} \cdot \dbinom{11}{10} \cdot \dbinom{12}{1} &\equiv 5\cdot 11 \cdot 12 \\ &\equiv 5 \cdot (-2) \cdot (-1) \\&= 10, \end{aligned}$$ implying the remainder is 10. $_\square$

Note: Looking deeper, it is possible to further explore these coefficients throughout Pascal's triangle.

Find a formula for the number of entries in the $n^\text{th}$ row of Pascal's triangle that are not divisible by $p$, in terms of the base-$p$ expansion of $n$.

---

Write $n = n_kp^k + \cdots + n_0$, $r = r_kp^k + \cdots + r_0$. Then $\binom{n}{r}$ is not divisible by $p$ if and only if $r_i \le n_i$ for $0 \le i \le k$. There are $n_i+1$ choices for each $r_i$ (it can be $0,1,\ldots,n_i$). So the answer is $$\prod_{i=0}^k (n_i+1). \ _\square$$

Note that in particular if $n = p^{k+1}-1$, then all the $n_i$ are equal to $p -1$, so the product is $p^{k+1}$; that is, all $p^{k+1}$ of the entries in the $\left(p^{k+1}-1\right)^\text{th}$ row are not divisible by $p$.

In fact, for the previous example, taking $p=2$ gives the following result:

Picture for $p=2$: If we draw a picture of the odd entries in the $n^\text{th}$ row of Pascal's triangle ($p=2$), we get an image that looks very much like the Sierpinski gasket:

source: http://ecademy.agnesscott.edu/~lriddle/ifs/siertri/pascalmath.htm

This fractality comes from the fact that if $k \le a < 2^n$, then $$\binom{a}{k} \equiv \binom{a+2^n}{k} \equiv \binom{a+2^n}{k+2^n} \ (\text{mod} \ 2)$$ by Lucas' theorem, so the top $2^n$ rows are reproduced twice side-by-side in the next $2^n$ rows.
What about the middle section? This consists of elements of the form $\binom{a+2^n}{r} ,$ where $a < r < 2^n$. In this case, since $r > a$, at least one of the binary digits of $r$ will be greater than the corresponding binary digit of $a$, so that part of the product in Lucas' theorem will be $\binom{0}{1} \equiv 0$, so all of the entries in the middle section will be even.

Show that $\binom{n}{p} \equiv \left\lfloor \frac{n}{p} \right\rfloor \pmod p$.

---

Let $n = n_k p^k + \cdots +n_1 p +n_0$ be the expansion of $n$ in base $p$. Then Lucas' theorem says $$\binom{n}{p} \equiv \binom{n_1}1 \binom{n_0}0 \equiv n_1 \ (\text{mod} \ p)$$ and $\left\lfloor \frac{n}{p} \right\rfloor = n_k p^{k-1} + \cdots + n_1 \equiv n_1 \pmod p$, so both sides are equal. $_\square$

There are several proofs, but the most down-to-earth one proceeds by induction. The idea is to write $n = Np+n_0, k = Kp+k_0$ by the division algorithm, and then to prove that $$\binom{Np+n_0}{Kp+k_0} \equiv \binom{N}{K} \binom{n_0}{k_0} \ (\text{mod}\ p),$$ where $0 \le n_0,k_0 < p$. The result will follow by induction since $N,K$ are smaller than $n,k$, respectively, and the base-$p$ expansions of $N$ and $K$ are just the base-$p$ expansions of $n$ and $k$ with the respective rightmost digits omitted.

To see that the formula above is true, write the left side as $$\frac{(Np+n_0)(\cdots)((N-K)p+n_0-k_0+1)}{(Kp+k_0)!},$$ and separate out the first $k_0$ terms on top and bottom. These are $$\frac{(Np+n_0)(\cdots)(Np+n_0-k_0+1)}{(Kp+k_0)(\cdots)(Kp+1)}.$$ The denominator is not divisible by $p$, so this is just $\binom{n_0}{k_0}\pmod p$.

Now the remaining terms come in consecutive groups of $p$; in each group of $p$ there is one term on top and on bottom that is divisible by $p$, and the rest are products of every nonzero element mod $p$, i.e. $(p-1)!$ mod $p$. The $(p-1)!$ on top and on bottom will cancel mod $p$, and we can take the $p$ factors out of each of the terms divisible by $p$. What is left is $$\begin{cases} \frac{N(N-1)(\cdots)(N-K+1)}{K!} & \text{if} \ n_0 \ge k_0 \\ \frac{(N-1)(N-2)(\cdots)(N-K)}{K!} & \text{if} \ n_0 < k_0 . \end{cases}$$ So we get $$\binom{n}{k} = \begin{cases} \binom{N}{K} \binom{n_0}{k_0} & \text{if} \ n_0 \ge k_0 \\ \binom{N-1}{K} \binom{n_0}{k_0} & \text{if} \ n_0 < k_0, \end{cases}$$ but in the second case, this also equals $\binom{N}{K} \binom{n_0}{k_0}$ because both are $0$. So the theorem is true by induction. $_\square$