Lucas Theorem – Proof and Applications
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.
| # | Steps | Comments |
|---|---|---|
| 1 | When $K=0$, $\binom{P}{K} \not \equiv 0 \mod P$ | Why is that? Well, $\binom{P}{K} = 1$ and a prime can never divide it. |
| 2 | Similarly, when $K=P$, $\binom{P}{K} \not \equiv 0 \mod P$ | Same reason. $\binom{P}{P} = 1$ and it cannot be divided by $P$. |
| So what about when $1 \leq K < P$ ? | ||
| 3 | We know that, $\binom{P}{K} = \frac{P!}{K!\times (N-K)!}$ | |
| 4 | or, $\binom{P}{K} = \frac{P \times (P-1) \times (P-2) \dots \times (P-K+1)}{K!}$ | |
| 5 | or, $\binom{P}{K} = P \times \left(\frac{(P-1) \times (P-2) \dots \times (P-K+1)}{K!}\right)$ | I extracted out the term $P$. Now tell me, is there any factor in $K!$ that can divide $P$ at all? |
| No. Since $K < P$, according to definition of a prime number, there is no number smaller than it that can divide it. | ||
| So, $\binom{P}{K}$ is a multiple of $P$ and there is no denying it. | ||
| 6 | $\therefore \binom{P}{K} \equiv 0 \mod P$, when $1 \leq K < P$ | Proved 🙂 |
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.
| # | Steps | Comments |
|---|---|---|
| 1 | $(1 + X )^P \mod P$ | We start from this. Let’s try to expand the expression. |
| 2 | $(1 + X)^P \equiv \binom{P}{0}X^0 + \binom{P}{1}X^1 + \binom{P}{2}X^2 \dots + \binom{P}{P}X^P \mod P$ | |
| We know that $\binom{P}{0} = \binom{P}{P} = 1$ | ||
| 3 | $(1 + X)^P \equiv 1 + \binom{P}{1}X^1 + \binom{P}{2}X^2 \dots + X^P \mod P$ | |
| From Lucas Lemma we know that $\binom{P}{K} \equiv 0 \mod P$ when $1 \leq K < P$ | ||
| 4 | $(1 + X)^P \equiv 1 + 0 \times X^1 + 0 \times X^2 \dots + X^P \mod P$ | |
| 5 | $\therefore (1 + X)^P \equiv 1 + X^P \mod P$ | Proved 🙂 |
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$?
| # | Steps | Comments |
|---|---|---|
| 1 | We know, $(1 + X)^P \equiv 1 + X^P \mod P$ | This is our base case |
| So the lemma works when $a=1$. What about when $a=2$? | ||
| 2 | $(1 + X)^{P^2} \equiv \left((1 + X)^P\right)^P \mod P$ | We can use Lucas Polynomial Expansion Lemma to simplify $(1 + X)^P$ |
| 3 | $\equiv (1 + X^P)^P \mod P$ | How about we treat $X^P$ as some normal variable like $Y$ ? |
| 4 | $\equiv (1 + Y)^P \mod P$ | If we apply Lucas Polynomial Expansion Lemma on $(1+Y)^P$, then… |
| 5 | $\equiv 1 + Y^P \equiv 1 + (X^P)^P \mod P$ | |
| 6 | $\equiv 1 + X^{P^2} \mod P$ | |
| 7 | $\therefore (1 + X)^{P^2} \equiv 1 + X^{P^2}$ | |
| Well, how about we try to generalize it using $a = n$? Assuming that the lemma holds for when $a = n-1$, then we can show that: | ||
| 8 | $(1 + X)^{P^n} \equiv \left((1 + X)^{P^{n-1}}\right)^P$ | Since we are assuming that lemma holds when $a = n-1$, we can say that: |
| 9 | $or, (1 + X)^{P^n} \equiv (1 + X^{P^{n-1}})^P$ | If we treat $X^{P^{n-1}}$ as some normal variable $Y$ like before: |
| 10 | $or, (1 + X)^{P^n} \equiv (1 + Y)^P$ | |
| 11 | $or, (1 + X)^{P^n} \equiv 1 + Y^P \equiv 1 + (X^{P^{n-1}})^P$ | |
| 12 | $\therefore (1 + X)^{P^n} \equiv 1 + X^{P^n}$ | Proved 🙂 |
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.
| # | Steps | Comments |
|---|---|---|
| 1 | $$\sum_{K=0}^{N}\binom{N}{K}X^K \mod P$$ | Our starting point |
| Let’s try to expand it | ||
| 2 | $$\equiv \binom{N}{0}X^0 + \binom{N}{1}X^1 + \binom{N}{2}X^2 + \dots + \binom{N}{N}X^N \mod P$$ | Hey! That loks familiar. Isn’t that… |
| 3 | $$\equiv (1+X)^N \mod P$$ | |
| That’s great. We started from somewhere and ended with $(1+X)^N$. Before we can continue further, we first need to break down N a bit. | ||
| We first represent $N$ in it’s $P$-base form | ||
| 4 | $$N = n_0 + n_1P + n_2P^2 \dots +n_xP^x$$ | |
| 5 | $$or, N = \sum_{i=0}^{x}n_iP^i$$ | Great! Our $N$ is now ready to get substituted. Shall we get back to where we left off from? |
| We left off at $(1+X)^N \mod P$, so we will continue from there. | ||
| 6 | $$(1+X)^N \mod P$$ | If we substitute $N$ from previous step, then we get: |
| 7 | $$\equiv(1+X)^{ \sum_{i=0}^{x}n_iP^i} \mod P$$ | It’s hard to see what is happening. Maybe we need to expand a bit more? |
| 8 | $$\equiv(1+X)^{n_0 + n_1P + n_2P^2 \dots +n_xP^x} \mod P$$ | |
| 9 | $$\equiv(1+X)^{n_0} \times (1+X)^{n_1P} \times (1+X)^{n_2P^2} \times \dots (1+X)^{n_xP^x} \mod P$$ | Great. This expansion looks nice. Seems like we are dealing with product of terms here? |
| Shall we compress it again? | ||
| 10 | $$\equiv \prod_{i=0}^{x}(1+X)^{n_iP^i} \mod P$$ | Not bad! We are getting somewhere. |
| We know that $a^{bc} = \left(a^b\right)^c$ | ||
| 11 | $$\equiv \prod_{i=0}^{x}\left((1+X)^{P^i}\right)^{n_i} \mod P$$ | Hey! Is that $(1+X)^{P^i}$ ? |
| Great! We can apply “Extended Lucas Polynomial Expansion Lemma” here | ||
| 12 | $$\equiv \prod_{i=0}^{x}\left(1+X^{P^i}\right)^{n_i} \mod P$$ | So far so good. |
| How about we let $Y = X^{P^i}$ and try to expand again! | ||
| 13 | $$\equiv \prod_{i=0}^{x}\left(1+Y\right)^{n_i} \mod P$$ | Well, we know that $(1+Y)^a = \sum_{j=0}^{a}\binom{a}{j}Y^j$ |
| 14 | $$\equiv \prod_{i=0}^{x}\left( \sum_{j=0}^{n_i}\binom{n_i}{j}Y^j \right)\mod P$$ | |
| Now, in order to move forward we have to understand an important fact: what is $\sum_{j=0}^{n_i}\binom{n_i}{j}Y^j$ ? | ||
| It’s just the polynomial expansion of $(1+Y)^{n_i}$ right? Let’s write it down in more simplified form. | ||
| $\binom{n_i}{0}Y^0+\binom{n_i}{1}Y^1+ \dots + \binom{n_i}{n_i}Y^{n_i}$ | ||
| Now, what is $n_i$? I hope you didn’t forget that. $n_i$ is simply a digit of $N$ is its $P$-base form. | ||
| Since it’s a digit of a number in $P$ base form, we know that $0 \leq n_i < P$. | ||
| $\therefore P-1 \geq n_i$ and there is no doubt right? Then can we say that… | ||
| $$\sum_{j=0}^{n_i}\binom{n_i}{j}Y^j = \sum_{j=0}^{P-1}\binom{n_i}{j}Y^j$$ | ||
| Note that only the upper limit of the summation has changed from $n_i$ to $P-1$. Does that change anything at all? Previously in the original summation, $j$ was suppose to stop at $n_i$, but now, if $P-1$ is greater than $n_i$, then $j$ will continue until $P-1$. | ||
| As a result new terms will get added to our polynomial expansions. And what are those? $\binom{n_i}{j}Y^j$ where $j > n_i$. | ||
| But we know that if $j > n_i$, then $\binom{n_i}{j} = 0$. So it doesn’t matter! | ||
| we can safely assume $\sum_{j=0}^{n_i}\binom{n_i}{j}Y^j = \sum_{j=0}^{P-1}\binom{n_i}{j}Y^j$ | ||
| 15 | $$\equiv \prod_{i=0}^{x}\left( \sum_{j=0}^{P-1}\binom{n_i}{j}Y^j \right)\mod P$$ | |
| Now, the next step is going to be mind bending. Did you know… | ||
| Product of summations can be converted to Summation of Products? | ||
| $$\sum_{i \in A}i \times \sum_{j \in B} j = \sum_{i \in A j\in B} i \times j$$ | ||
| In order to see that it is true, simply imagine two set $A = {x,y,z}$ and $B = {p,q}$. If you have two summations on these sets and multiply them, then you have $(x+y+z) \times (p+q) = xp + xq + yp + yq + zp + zq$ | ||
| So our target is now to do same. We want to make product of summation into summation of product. For that we will need to expand the previous step. | ||
| Expanding the summation will get rid of of the loop with variable $i$. So, before we remove variable $i$, we have remove $Y$, because it has $i$ inside it. | ||
| So we first replace $Y$ with $X^{P^i}$ | ||
| 16 | $$\equiv \prod_{i=0}^{x}\left( \sum_{j=0}^{P-1}\binom{n_i}{j}X^{P^ij} \right)\mod P$$ | With $Y$ gone, we can now expand the summation. |
| 17 | $$\equiv \sum_{j=0}^{P-1}\binom{n_0}{j}X^{j} \times \sum_{j=0}^{P-1}\binom{n_1}{j}X^{P^1j} \times \dots \times \sum_{j=0}^{P-1}\binom{n_x}{j}X^{P^{x}j} \mod P$$ | We got rid of the product symbol at the beginning. |
| There are $x$ summations here. Using just $j$ makes things confusing. Let’s give each summation a unique variable so that it’s easier to reason with. | ||
| 18 | $$\equiv \sum_{j_0=0}^{P-1}\binom{n_0}{j_0}X^j \times \sum_{j_1=0}^{P-1}\binom{n_1}{j_1}X^{P^1j} \times \dots \times \sum_{j_x=0}^{P-1}\binom{n_x}{j_x}X^{P^xj} \mod P$$ | Ah much better. I can already see the end of the tunnel! |
| Let $Z$ be a set where $Z = {0, 1, 2, \dots P-1}$ | ||
| Then we can convert product of summation to summation of product | ||
| 19 | $$\equiv \sum_{j_0, j_1, j_2 \dots j_x \in Z}\binom{n_0}{j_0}X^{j_0} \binom{n_1}{j_1}X^{P^1j_1} \dots \binom{n_x}{j_x}X^{P^xj_x} \mod P$$ | That looks like product of something. Let’s compress it. |
| Notice that our previous equation no longer has $i$ in it anymore. We completely removed it. | ||
| Now, we are going to introduce $i$ variable again. | ||
| 20 | $$\equiv \sum_{j_0, j_1, j_2 \dots j_x \in Z} \left( \prod_{i=0}^{x} \binom{n_i}{j_i} X^{P^ij_i} \right) \mod P$$ | |
| We know that, $\prod ab = \prod a \times \prod b$ | ||
| 21 | $$\equiv \sum_{j_0, j_1, j_2 \dots j_x \in Z} \left( \prod_{i=0}^{x} \binom{n_i}{j_i} \prod_{i=0}^x X^{P^ij_i} \right) \mod P$$ | |
| Now, what is $\prod_{i=0}^x X^{P^ij_i}$? | ||
| If we exapand it: | ||
| 21.1 | $$\prod_{i=0}^x X^{P^ij_i} = X^{\sum_{i=0}^xP^ij_i}$$ | Next, what is $\sum_{i=0}^xP^ij_i$? |
| If you go back and take a look at step 4, then you will notice that $\sum_{i=0}^xP^ij_i$ is just a number in P-base. | ||
| Therefore, we can say that… | ||
| 21.2 | $$X^{\sum_{i=0}^xP^ij_i} = X^K$$ | where, $0 \leq K < M$. But what is $M$? |
| $M$ is the biggest number we can possibly make by choosing value of $j_i$ from $j_0,j_1,j_2…j_x \in Z$. | ||
| The biggest value we can make is by choosing every value of $j_i$ as $P-1$. | ||
| Hence, $M = (P-1) + (P-1)P + (P-1)P^2 + \dots + (P-1)P^x$ | ||
| Please note that, this means $M$ is greater than or equal to $N$ mentioned in step 4. | ||
| Hence, we can rewrite step 20 into… | ||
| 22 | $$\equiv \sum_{j_0, j_1, j_2 \dots j_x \in Z} \left( \prod_{i=0}^{x} \binom{n_i}{j_i} X^K \right) \mod P$$ | where, $K = j_0 + j_1P + \dots + j_xP^x$ |
| Now, note that any unique combination of $j_0,j_1,j_2 \dots j_x$ from set $Z$ simply creates a unique value for $m$, that ranges from $0$ to $M$. | ||
| 23 | $$\equiv \sum_{K=0}^M \left(\prod_{i=0}^{x} \binom{n_i}{j_i} X^K\right) \mod P$$ | where, $j_i$ is simply the digit of $m$ in its P-based form |
| We are almost finished. Next we just need to make the upper bound of the summation a little bit tighter. | ||
| Consider what will happen if $K > N$. | ||
| We know that $j_i$ are the digits of $K$ in P-based form and $n_i$ are the digits of $N$ is P-based form. | ||
| If, $K > N$, then there must a be a digit $j_i$ which is greater than $n_i$ for a particular $i$. | ||
| If that is the case, then $\binom{n_i}{j_i}$ will be 0 since $j_i > n_i$. | ||
| Hence, when $K > N$, $X^K \prod_{i=0}^{x} \binom{n_i}{j_i}$ will be 0. | ||
| Combining with the fact $N \leq M$, we can rewrite equation at 22 as… | ||
| 24 | $$\equiv \sum_{K=0}^N \left( \prod_{i=0}^{x} \binom{n_i}{j_i} X^K \right) \mod P$$ |
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
- $\binom{n}{k} \mod P$
This is the most straightforward application.Try solving CodeChef CHKSEL – Help with selection.
$\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.
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$.
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
- CodeChef CHKSEL – Help with selection
- SPOJ DCEPC13D – The Ultimate Riddle – Needs Chinese Remainder Theorem
- CodeChef LUCASTH – Lucas Theorem
- SPOJ DUKKAR – Dukkar and Pikka
- SPOJ HLP_RAMS – Topper Rama Rao