内容
对于一个质数 \(p\)，有：
\[\LARGE C_n^m \equiv C_{[\frac{n}{p}]}^{[\frac{m}{p}]}·C_{n \bmod p}^{m \bmod p} \pmod p \]证明
引理：\((1+x)^p \equiv (1+x^p) \pmod p\)
证明：根据二项式定理展开的：
\[(1+x)^p = 1+C_p^1·x+C_p^2·x^2+...+C_p^{p-1}·x^{p-1}+C_p^p · x^p \]对于任意一个 \(C_p^x\) ，其中 \(1 < x < p\)，可以得到：
\[C_p^x = \frac{p(p-1)(p-2)...(p-x+1)}{1\times2\times3...\times x} \]\(\because\) 连续的 \(x\) 个自然数的乘积能被 \(x\) 整除，\(\therefore\) \(\frac{(p-1)(p-2)...(p-x+1)}{1\times2\times3\times....\times x}\) 是整数，\(C_p^x\) 是 \(p\) 的倍数。
\(\therefore\) 上式在模 \(p\) 意义下：
\[1+C_p^1·x+C_p^2·x^2+...+C_p^{p-1}·x^{p-1}+C_p^p · x^p \equiv 1 + C_p^p ·x^p\equiv1+x^p \pmod p \]得证。
证明定理
我们先设 \(n = q_1·p + r_1, m=q_2·p+r_2\) 。
然后我们考虑 \((1+x)^n\) 这个式子在模 \(p\) 意义下：
\[(1+x)^n \equiv (1+x)^{q_1·p+r_1} \pmod p \]根据乘方的性质，我们可以得到：
\[(1+x)^n \equiv [(1+x)^{p}]^{q_1} \times(1+x)^{r_1} \pmod p \]再由引理可得：
\[(1+x)^n \equiv (1+x^p)^{q_1} \times (1+x)^{r_1} \pmod p \]把两边根据二项式定理展开后，左边必有一项为 \(C_{q_1}^{q_2}·x^{q_2·p}\) ，右边必有一项为 \(C_{r_1}^{r_2}·x^{r_2}\) ，则两者的乘积为 \(C_{q_1}^{q_2}·C_{r_1}^{r_2}·x^{q_2·p+r_2}\) ，因为 \(q_2·p+r_2=m\) ，所以这一项就是 \(C_{q_1}^{q_2}·C_{r_1}^{r_2}·x^m\)。
因为 \(p\) 是定值，所以 \(q_2\) 与 \(r_2\) 相当于 \(m\) 除以 \(p\) 的商和余数，只有一种情况，故 \(m\) 次项的系数就是 \(C_{q_1}^{q_2}·C_{r_1}^{r_2}\)。
我们再把 \((1+x)^n\) 这个式子直接二项式定理展开，会发现 \(m\) 次项的系数是 \(C_n^m\) ，故可以得到：
\[C_n^m \equiv C_{q_1}^{q_2}·C_{r_1}^{r_2} \pmod p \]其实就是：
\[ C_n^m \equiv C_{[\frac{n}{p}]}^{[\frac{m}{p}]}·C_{n \bmod p}^{m \bmod p} \pmod p \]得证。
标签：frac,pmod,定理,笔记,times,卢卡斯,bmod,equiv From： https://www.cnblogs.com/rlc202204/p/16949471.html