Proof of Lucas' theorem
The Theorem
对于非负整数 $n, m$ 和质数 $p$，有
$$ C_{n}^{m} \equiv C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_0}^{m_0} \pmod p \tag{1} $$
其中，
$$ \begin{eqnarray} n = n_kp^k + n_{k - 1}p^{k - 1} + \cdots + n_1p + n_0 \tag{2} \\\ m = m_kp^k + m_{k - 1}p^{k - 1} + \cdots + m_1p + m_0 \tag{3} \end{eqnarray} $$
分别是 $n,m$ 的 $p$ 进制展开，$k$ 为非负整数，$0 \le n_i, m_i \le p - 1$。
Inference
由式 $(2), (3)$ 得
$$ \begin{eqnarray} n \bmod p = n_0 \tag{4} \\\ m \bmod p = m_0 \tag{5} \\\ \lfloor \frac{n}{p} \rfloor = n_kp^{k - 1} + n_{k - 1}p^{k - 2} + \cdots + n_1 \tag{6} \\\ \lfloor \frac{m}{p} \rfloor = m_kp^{k - 1} + m_{k - 1}p^{k - 2} + \cdots + m_1 \tag{7} \end{eqnarray} $$
将定理运用到式 $(6), (7)$ 上，有
$$ C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \equiv C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_1}^{m_1} \pmod p \tag{8} $$
将式 $(4), (5), (8)$ 代入式 $(1)$ 得
$$ C_{n}^{m} \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} C_{n \bmod p}^{m \bmod p} \pmod p \tag{9} $$
The Proof
对于质数 $p$ 和整数 $k$，当 $1 \le k \le p - 1$ 时，有
$$ C_{p}^{k} = \frac{p \cdot (p - 1) \cdots (p - k + 1)}{k \cdot (k - 1) \cdots 1} \tag{10} $$
由于分母的每一项都与 $p$ 互质，因此 $C_{p}^{k} \bmod p = 0$。进而
$$ \begin{array} \left (1 + X)^p & = C_p^0 + C_p^1X + C_p^2X^2 + \cdots + C_p^{p - 1}X^{p - 1} + C_p^pX^p \\\ & \equiv 1 + X^p \pmod p \tag{11} \end{array} $$
下面用数学归纳法证明 $(1 + X)^{p^i} \equiv 1 + X^{p^i} \pmod p$ 对于任意正整数 $i$ 都成立。
- 已证 $i = 1$ 时，上式成立。
假设当 $i = k$ 时，上式成立，则当 $i = k + 1$ 时，
$$ \begin{array} \left (1 + X)^{p^{k + 1}} &= [(1 + X)^{p^k}]^p \\\ &\equiv (1 + X^{p^k})^p \pmod p,\ 令 X^\prime = X^{p^k}，运用式 (11) \\\ &\equiv 1 + (X^{p^k})^p \pmod p \\\ &\equiv 1 + X^{p^{k + 1}} \pmod p \tag{12} \end{array} $$
由此得证。进而
$$ \begin{array} \left (1 + X)^n & = (1 + X)^{n_kp^k + n_{k - 1}p^{k - 1} + \cdots + n_1p + n_0} \\\ & = (1 + X)^{n_kp^k} \cdot (1 + X)^{n_{k - 1}p^{k - 1}} \cdots (1 + X)^{n_{1}p} \cdot (1 + X)^{n_{0}} \\\ & \equiv (1 + X^{p^k})^{n_k} \cdot (1 + X^{p^{k - 1}})^{n_{k - 1}} \cdots (1 + X^p)^{n_{1}} \cdot (1 + X)^{n_{0}} \bmod p \tag{13} \end{array} $$
式 $(13)$ 的左边 $X^m$ 的系数为 $C_n^m$，结合式 $(3)$ 可验证右边 $X^m$ 的系数为
$$ C_{n_k}^{m_k} C_{n_{k -1}}^{m_{k - 1}} \cdots C_{n_1}^{m_1} C_{n_0}^{m_0} \tag{14} $$
由于左右两边系数一定相等，因此式 $(1)$ 成立。显然，当 $n < m$ 时，必存在 $n_i < m_i$，此时左右两边系数都为 $0$，等式仍然成立。