定理
对于非负整数 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。
推论
由式 (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}
定理证明
对于质数 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,等式仍然成立。