Lucas theorem states that

Let $m,n$ be two natural numbers, $p$ be a prime. Suppose that $m, n$ admit the following base $p$ representation $$m=m_0+m_1p+\cdots+m_sp^s,\qquad n=n_0+n_1p+\cdots+n_sp^s$$ with $0\le m_i, n_i \le p-1$, then $$\binom{n}{m}\equiv\prod_{i=0}^{s}\binom{n_i}{m_i}\ (\bmod p)$$

I have read the proof of Lucas' Theorem on Wikipedia and in this paper. There are some steps that I don't fully understand. It is follows

\begin{align*} \sum^{n}_{m=0}\binom{n}{m}X^m&=(1+X)^n=\prod_{i=0}^{s}\left( (1+X)^{p^i}\right)^{n_i}\\ &\equiv \prod_{i=0}^{s}(1+X^{p^i})^{n_i}=\prod_{i=0}^{s}\left( \sum_{m_i=0}^{n_i}\binom{n_i}{m_i}X^{m_ip^i}\right)\ (\bmod p)\\ &=\prod_{i=0}^{s}\left(\sum_{m_i=0}^{p-1}\binom{n_i}{m_i}X^{m_ip^i} \right)\\ &=\sum_{m=0}^{n}\left(\prod_{i=0}^{s}\binom{n_i}{m_i} \right)X^m\ (\bmod p) \end{align*}

How can we get \begin{align*} &\prod_{i=0}^{s}\left( \sum_{m_i=0}^{n_i}\binom{n_i}{m_i}X^{m_ip^i}\right) \\ &=\prod_{i=0}^{s}\left(\sum_{m_i=0}^{p-1}\binom{n_i}{m_i}X^{m_ip^i} \right)\\ &=\sum_{m=0}^{n}\left(\prod_{i=0}^{s}\binom{n_i}{m_i} \right)X^m \end{align*}

I don't know how can we change the index from $n_i$ to $p-1$ in the first equation and how can we get the second equation.

Please explain for me.


  • $\begingroup$ $m_i$ has two different meanings: In some places it's a constant depending on $m$; in other places it's a variable being summed over, and may as well be called $k$. $\endgroup$ – mr_e_man Jan 28 at 2:24

For the first line, observe that $${n_i\choose k}=0$$ for $k>n_i$. So, \begin{align*} \sum_{m_i=0}^{n_i}\binom{n_i}{m_i}X^{m_ip^i} =\sum_{m_i=0}^{p-1}\binom{n_i}{m_i}X^{m_ip^i} \end{align*} , as the extra terms are basically zero.

For the second line, notice that $m$ can be uniquely written in the form $$m_0'+m_1'p+\ldots+m_s'p^s$$

Thus, the coefficient of $X^m$ in \begin{align*} \prod_{i=0}^{s}\left(\sum_{m_i=0}^{p-1}\binom{n_i}{m_i}X^{m_ip^i} \right) \end{align*} will be the product of the coefficients of $X^{m_ip^i}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.