Lucas' Theorem

Theorem

Let $p$ be a prime number.

Let $n, k \in \Z$.

Then:

$\displaystyle \binom n k \equiv \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {n \bmod p} {k \bmod p} \pmod p$

where:

• $\displaystyle \binom n k$ is a binomial coefficient;
• $n \bmod p$ denotes the modulo operation;
• $\left \lfloor \cdot \right \rfloor$ is the floor function.

Hence, if the representation of $n$ and $k$ to the base $p$ are given by:

• $n = a_r p^r + \cdots + a_1 p + a_0$
• $k = b_r p^r + \cdots + b_1 p + b_0$

then:

$\displaystyle \binom n k \equiv \prod_{j=0}^r \binom {a_j} {b_j} \pmod p$

Proof

Proof of first part

First we show that:

$\displaystyle \binom n k \equiv \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {n \bmod p} {k \bmod p} \pmod p$.

Consider $\displaystyle \binom n k$ as the fraction $\displaystyle \frac {n \left({n-1}\right) \left({n-2}\right) \cdots \left({n-k+1}\right)} {k \left({k-1}\right) \left({k-2}\right) \cdots 1}$.

This can be expressed as:

$\displaystyle (1) \qquad \binom n k = \left({\frac n k}\right) \left({\frac {n-1}{k-1}}\right) \left({\frac {n-2}{k-2}}\right) \cdots \left({\frac {n-k+1}{1}}\right)$.

Let $k = s p + t$ from the Division Theorem; thus $t = k \bmod p$.

The denominators of the first $t$ factors in $(1)$ do not have $p$ as a divisor.

Now let $n = u p + v$, again from the Division Theorem; thus $v = n \bmod p$.

Now, when we deal with non-multiples of $p$, we can work modulo $p$ in both the numerator and denominator, from Common Factor Cancelling in Congruence.

So we consider the first $t$ factors of $(1)$ modulo $p$:

These are:

$\displaystyle \left({\frac {u p + v}{s p + t}}\right) \left({\frac {u p + v-1}{s p + t-1}}\right) \cdots \left({\frac {u p + v-t+1}{s p + 1}}\right) \equiv \left({\frac v t}\right) \left({\frac {v-1}{t-1}}\right) \cdots \left({\frac {v-t+1} 1}\right) \pmod p$

So, these first $t$ terms of $(1)$ taken together are congruent modulo $p$ to the corresponding terms of:

$\displaystyle \binom {n \bmod p} {k \bmod p}$

These differ by multiples of $p$.

So we are left with $k - k \bmod p$ factors.

These fall into $\left \lfloor {k / p} \right \rfloor$ groups, each of which has $p$ consecutive values.

Each of these groups contains exactly one multiple of $p$.

The other $p-1$ factors in a given group are congruent (modulo $p$) to $\left({p-1}\right)!$ so they cancel out in numerator and denominator.

We now need to investigate the $\left \lfloor {k / p} \right \rfloor$ multiples of $p$ in the numerator and denominator.

We divide each of them by $p$ and we are left with the binomial coefficient:

$\displaystyle \binom{\left \lfloor {\left({n - k \bmod p}\right) / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor}$

Now, if $k \bmod p \le n \bmod p$, this equals:

$\displaystyle \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor}$

Otherwise, if $k \bmod p > n \bmod p$, the other factor:

$\displaystyle \binom {n \bmod p} {k \bmod p}$

is zero.

So the formula holds in general.

Proof of second part

Now we consider the representation of $n$ and $k$ to the base $p$:

• $n = a_r p^r + \cdots + a_1 p + a_0$
• $k = b_r p^r + \cdots + b_1 p + b_0$

Let $n_1 = \left \lfloor {n / p} \right \rfloor, k_1 = \left \lfloor {k / p} \right \rfloor$.

We have that:

• $n \bmod p = a_0, k \bmod p = b_0$;
• $n_1 = a_r p^{r-1} + a_{r-1} p^{r-2} \cdots + a_1, k_1 = b_{r-1} p^{r-2} \cdots + b_1$.

From the proof of the first part, this gives us:

$\displaystyle \binom n k \equiv \binom {n_1} {k_1} \binom {a_0} {b_0} \pmod p$

Now we do the same again to the representation to the base $p$ of $n_1$ and $n_2$.

Thus:

$\displaystyle \binom n k \equiv \binom {\left \lfloor {n_1 / p} \right \rfloor} {\left \lfloor {k_1 / p} \right \rfloor} \binom {a_1} {b_1} \binom {a_0} {b_0} \pmod p$

And so on until $\left \lfloor {n_r / p} \right \rfloor$ and $\left \lfloor {k_r / p} \right \rfloor$.

Hence the result.

$\blacksquare$

Source of Name

This entry was named for Édouard Lucas.

It appears in his 1878 paper Théorie des Fonctions Numériques Simplement Périodiques in the American Journal of Mathematics Volume 1, issues 2 - 4.

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.6$: Exercise $10 \ \text{e, f}$