Problem

Given non-negative integers $N$, $K$ and a prime number $P$, find the value of:

$$\binom{N}{K} \mod P$$

Sounds like a simple problem right? There are several ways to solve the problem, depending on the constraints of $N$, $K$, and $P$.

• Direct: If $N$, $K$ are really small, less than $12$, then we can calculate $\binom{N}{K}$ directly using formula $\frac{N!}{K! \times (N-K)!}$ and find the mod $P$ value. Not gonna work when the values are around $1000$.
• DP: If they are slightly bigger but still around $1000$, then we can use dynamic programming to find the result, using the recurrence: $\binom{N}{K} = \binom{N-1}{K} + \binom{N-1}{K-1}$. Not going to work if values are around $10^5$.
• Modular Inverse: If $P$ is a large prime, say $10^9+7$, then using modular inverse and some precalculation we can still calculate $\frac{N!}{K! \times (N-K)!}$. But still, we will need to run $O(N)$ loop to calculate $N!$. Not going to work if $N$ is too large. Also, if $P$ is small then there won’t be any modular inverse since $P$ will not be coprime with denominator anymore.

So what do we do when $N$ and $K$ are large (let’s say around $10^9$) and prime $P$ is small, let’s say $37$. Is it still possible?

Of course. We use Lucas Theorem.

Lucas Theorem

Given $N$, $K$ and prime $P$, if we write $N$ and $K$ in base $P$ form as:

$N = n_0 + n_1 \times P + n_1 \times P^2 + \dots + n_x \times P^x$
$K = k_0 + k_1 \times P + k_1 \times P^2 + \dots + k_x \times P^x$

where $x$ is some non-negative number and $0 \leq n_i, k_i < P$ for $0 \leq i \leq x$, then

$$\binom{N}{K} \equiv \prod_{i=0}^{x}\binom{n_i}{k_i} \mod P$$

I hope you didn’t forget how to write a number in another base. If you did forget, then read Introduction to Number System for a quick refresher.

How does this theorem help us in calculating $\binom{N}{K}$?

• It says that we can break a binomial coefficient with large $N$ and $K$ into a product of smaller binomial coefficients.
• Here $n_i$ and $k_i$ are smaller than $P$.
• If $P$ is small enough, then we can use dynamic programming to calculate $\binom{n_i}{k_i} \mod P$.
• But how many smaller binomial coefficients do we have to multiply? We have to multiply $x$ binomial coefficients, where $x$ is the number of digits $N$ and $K$ have in their $P$ base form. To be exact, $x = log_P(N)$.
• So if we precalculate the smaller binomial coefficients, then we can find $\binom{N}{K}$ in $O(log(N))$.

So using Lucas Theorem we are able to solve the problem mentioned above. With this, we now have another tool in our pocket to calculate $\binom{N}{K}$. Wonderful.

Proof

Please note that you don’t have to understand the proof in order to use the theorem. You can skip this section and just go for the “Applications” section directly if you want. I suggest you don’t skip since the proof is really interesting.

Before we dive into proof of Lucas theorem, we first need to proof a helping lemma. I don’t know the name of the lemma so how about we call it “Lucas Lemma” for easier reference? I always found a name easier to reason with than “Lemma 1.1”.

Lucas Lemma

Lemma: $\binom{P}{K}$ is always divisible by $P$ as long as $P$ is prime and $1 \leq K < P$.

This is actually very easy to prove.

That wasn’t very hard. Was it?

Next, we will look into another lemma required for proving Lucas Theorem. Again, there is no name for it so I will call it “Lucas Polynomial Expansion Lemma”.

Lucas Polynomial Expansion Lemma

Lemma: $(1+X)^P \equiv 1 + X^P \mod P$, where $P$ is a prime.

This is trivial to prove now that we already know Lucas Lemma.

Just one more lemma before we start with the theorem.

Extended Lucas Polynomial Expansion Lemma

Lemma: $(1+X)^{P^a} \equiv 1 + X^{P^a} \mod P$, where $P$ is a prime and $a$ is any non-negative integer.

Well, this one can be easily proved using induction.

Let us start with the base case. What happens when $a = 1$?

So, as long as the lemma holds true for $a=n-1$, it will also hold true for $a = n$. Since we already showed that the lemma holds true for $a = 1$ and $a = 2$, we can say for sure that it will hold true for $a > 1$.

With that, our proof by induction is complete and we are finally ready to tackle proof of Lucas Theorem.

Lucas Theorem Continued

In short Lucas theorem states that:

$$\binom{N}{K} \equiv \prod_{i=0}^{x}\binom{n_i}{k_i} \mod P$$

where $N$ and $K$ are non-negative numbers, $P$ is a prime and $n_i$, $k_i$ represents digits of $N$ and $K$ in $P$-base form.

In order to prove this theorem, we need to start from a place which will seem really confusing at first. When you see the starting position you will probably ask, “Huh? What is this? Why are we starting from here?”. And I understand your feeling. I felt the same.

But that’s how it is. The person who came up with the proof probably spent many hours in trial and error until finally discovering this starting point. Even though we don’t know how he found this starting point, we know that it leads us to our destination: the proof of Lucas Theorem.

So what is this mysterious starting point? It’s this:

$$\sum_{K=0}^{N}\binom{N}{K}X^K \mod P$$
Without further delay, let us see the steps of the proof.

And we are done!

Let’s compare our starting and ending points now.

$$\sum_{K=0}^{N}\binom{N}{K}X^K \equiv \sum_{K=0}^N \left( \prod_{i=0}^{x} \binom{n_i}{j_i} X^K \right) \mod P$$

Since the two polynomials are equivalent, their coefficients must be equivalent. Hence:

$$\binom{N}{K} \equiv \prod_{i=0}^{x} \binom{n_i}{j_i} \mod P$$ , where $n_i$ are digits of $N$ and $j_i$ are digits of $K$ in P-based form. Proved.

Applications of Lucas Theorem

1. $\binom{n}{k} \mod P$
    
   This is the most straightforward application.

   Try solving CodeChef CHKSEL – Help with selection.

2. $\binom{n}{k} \mod M$, where $M$ is multiple of two primes

   Often time, problem requires us to find $\binom{n}{k} \mod M$, where $M$ is not a prime. As a result we are unable to use modular inverse. But it will also be given that $M = pq$, where $p$ and $q$ are small primes. In this scenario, we can use lucas theorem to find $\binom{n}{k} \mod p$ and $\binom{n}{k} \mod q$ and then use Chinese Remainder Theorem to combine the result to get $\binom{n}{k} \mod pq$.

   Try solving SPOJ DCEPC13D – The Ultimate Riddle.

3. Number of elements divisible by $P$ in $n_{th}$ row of Pascal Triangle

   This is a very interesting application of Lucas Theorem. From Lucas Theorem, we know that we can break down $\binom{n}{k}$ to a product of $\binom{n_i}{k_i}$. Now, whenever $k_i > n_i$, the product will be zero.

   So, in the $n_{th}$ row of pascal triangle, if we want to know how many values of $k$ gives us $\binom{n}{k} \not \equiv 0 \mod P$, where $n = n_0 + n_1P + n_2P^2 + \dots + n_xP^x$, then answer is $\prod_{i=0}^xn_i+1$.

   Try solving CodeChef LUCASTH – Lucas Theorem , SPOJ DUKKAR – Dukkar and Pikka.

   For example, how many odd numbers are there in $14$th row of pascal triangle? This means we need to find solution to the following equation $\binom{14}{x} \not \equiv 0 \mod 2$. If we express $14$ in binary we get $(14)_{10} = (1010)_2$. Hence result is $2^2$.

4. Number of odd elements in $n_{th}$ row of Pascal Triangle

   Answer is $2^x$, where $x$ is number of $1$ bit in binary representation of $n$ (pop-count).

   Try solving SPOJ HLP_RAMS – Topper Rama Rao.

Conclusion

The first time I tried to understand the proof of Lucas Theorem from Wikipedia page, it took me 2 days. The proof on the wiki is just 6-7 lines long. It’s very compact with tons of hidden lines in between. By the time I figured out all the hidden lines, the proof became this big.

There is another proof for Lucas Theorem that uses induction. I decided to go for the algebraic one because it felt more fun.

Anyways, I hope you enjoyed reading the proof as much as I struggled to write it. If you notice any mistakes, please let me know in the comments.

Related Problems

1. CodeChef CHKSEL – Help with selection
2. SPOJ DCEPC13D – The Ultimate Riddle – Needs Chinese Remainder Theorem
3. CodeChef LUCASTH – Lucas Theorem
4. SPOJ DUKKAR – Dukkar and Pikka
5. SPOJ HLP_RAMS – Topper Rama Rao

• Category: Combinatorics, CPPS
• Tag: problem-list, proof, theorem