定义
对于任意质数p
$\Huge C_m^n\equiv C_{\biggl\lfloor\frac{m}{p}\biggr\rfloor}^{\biggl\lfloor\frac{n}{p}\biggr\rfloor}*C_{m\ mod\ p}^{n\ mod\ p}\ \ (MOD\ p)$
证明
对于任意质数p都有
$\huge C_p^i\equiv0\ MOD\ p(i\not= 0\&\&i\not=p)$
通过二项式定理，我们可得
$\huge (x+1)^p=\sum\limits_{i=0}^pC_p^ix^i$
因为$\huge C_p^i\equiv0\ MOD\ p(i\not= 0\&\&i\not=p)$
所以$\huge (x+1)^p\equiv x^p+1\ (MOD\ p)$
于是我们对于任意正整数m有
$\huge (x+1)^m=(x+1)^{\biggl\lfloor\frac{m}{p}\biggr\rfloor*p}*(x+1)^{m\ mod\ p}\equiv (x^p+1)^{\biggl\lfloor\frac{m}{p}\biggr\rfloor}*(x+1)^{m\ mod\ p}\ (MOD\ p)$
用二项式定理展开就是
$\huge \sum\limits_{i=0}^mC_m^ix^i\equiv \sum\limits_{i=0}^{\biggl\lfloor\frac{m}{p}\biggr\rfloor}C_{\biggl\lfloor\frac{m}{p}\biggr\rfloor}^ix^{i*p}*\sum\limits_{i=0}^{m\ mod\ p}C_{m\ mod\ p}^ix^i\ (MOD\ p)$
当x指数为n的项就为,
$\huge C_m^nx^n\equiv C_{\biggl\lfloor\frac{m}{p}\biggr\rfloor}^{\biggl\lfloor\frac{n}{p}\biggr\rfloor}x^{\biggl\lfloor\frac{m}{p}\biggr\rfloor*p}*C_{m\ mod\ p}^{n\ mod\ p}x^{n\ mod\ p}\ (MOD\ p)$
两边约去x的n次方就为
$\huge C_m^n\equiv C_{\biggl\lfloor\frac{m}{p}\biggr\rfloor}^{\biggl\lfloor\frac{n}{p}\biggr\rfloor}*C_{m\ mod\ p}^{n\ mod\ p}\ \ (MOD\ p)$