# On the proof of Lucas' theorem

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.

Thanks

## 1 Answer

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}$.