引理1:\(x^p \equiv x (\bmod p)\)，\(p\)是素数（费马小定理）
证明略
引理2:\((a + b)^n = \sum_{i = 0}^n \binom{n}{i} a^i b^{n - i}\)
证明略
定理1:\((x + 1)^p \equiv x + 1 \equiv x^p + 1 (\bmod p)\)
由引理1可得
定理2:\(\binom{n}{m} \equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \binom{n \bmod p}{m \bmod p} (\bmod p)\)
证明:
\((x + 1)^n \equiv (x + 1)^{\lfloor \frac{n}{p} \rfloor \times p} \times (x + 1)^{n \bmod p} \equiv (x^p + 1)^{\lfloor \frac{n}{p} \rfloor \times p} \times (x + 1)^{n \bmod p} (\bmod p)\)
两边用二项式定理展开，
得\(\sum_{i = 0}^n \binom{n}{i} x^i \equiv (\sum_{i = 0}^{\lfloor \frac{n}{p} \rfloor} \binom{\lfloor \frac{n}{p} \rfloor}{i} x^{ip}) \times (\sum_{i = 0}^{n \bmod p} \binom{n \bmod p}{i}) x^i \equiv (\sum_{i = 0}^{\lfloor \frac{n}{p} \rfloor} \binom{\lfloor \frac{n}{p} \rfloor}{i} x^{ip}) \times (\sum_{i = 0}^{p - 1} \binom{n \bmod p}{i}) x^i (\bmod p)\)
所以\(\binom{n}{i} x^i \equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{i}{p} \rfloor} x^{\lfloor \frac{i}{p} \rfloor \times p} \times \binom{n \bmod p}{i \bmod p} x^{i \bmod p}\)
证毕
原文：https://www.cnblogs.com/tkandi/p/10416771.html