求证

$$C_{m}^{n}≡\prod_{i=0}^{k}C_{m_i}^{n_i}\mod p$$
其中 $m=\sum_{i=0}^{k}m_ip^i$， $n=\sum_{i=0}^{k}n_ip^i$
p是质数。

首先，我们知道，$n_0=n \mod p，m_0=m \mod p$
那么原式相当于求证

$$C_m^n≡C_{\lfloor{m\over p}\rfloor}^{\lfloor{n\over p}\rfloor}*C_{m \mod p}^{n \mod p} \mod p$$
这样就可以归纳一发证明整个定理了。

首先我们知道，对于任意的质数p

$$C_{p}^{n}≡0\mod p，(n\not =0或p)$$
这个式子是恒成立的。
那么我们对于任意的一个实数x有 $$(x+1)^p=\sum_{i=0}^{p}C_p^ix^i$$
在模p意义下有 $$(x+1)^p≡(x^p+1)\mod p$$

Ps:为了方便接下来的所有计算均在模p意义下进行。

我们对于任意一个整数m有

$$(x+1)^m=(x+1)^{\lfloor{m\over p}\rfloor p}*(x+1)^{m\mod p}$$
$$(x+1)^m=(x^p+1)^{\lfloor{m\over p}\rfloor}*(x+1)^{m\mod p}$$
二项式定理展开
$$\sum_{i=0}^{m}C_{m}^{i}x^i=(\sum_{i=0}^{\lfloor{m\over p}\rfloor}C_{\lfloor{m\over p}\rfloor}^{i}x^{pi})(\sum_{i=0}^{m\mod p}C_{m\mod p}^{i}x^i)$$
那么等号左边当i=n时，等号右边唯一能组合出来x^n的就是x^(n\p*p)和x^(n mod p)
那么系数乘积也就相等。
证毕。