# 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 \)?

## Statement of the Theorem

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.

## Applications

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{align} \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{align}\] implying the remainder is 10. \(_\square\)

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

The oranges are stacked as a triangular-based pyramid such that there is one orange on the top, 2 more oranges on the second layer, yet 3 more oranges on the third, and so on until there are 200 pyramidal layers of oranges.

If this big lot is distributed into boxes of 7 oranges each, how many oranges will remain undistributed?

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: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 \)

These are the first few rows of Pascal's triangle:

Each number is derived by adding up the two numbers just above it (and to the left and right) in the previous row. (The numbers on the ends remain 1).

Of the first 1000 rows, as labeled above, how many of them contain all odd numbers?

**Image credit:** http://www.daviddarling.info/

## Proof of the Theorem

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 binary expansions of \( N \) and \( K \) are just the binary 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 \)