定理：$\forall a, b \in \Z, n \in \Z^+$：
$$ (a+b)^n = \sum_{i=0}^n \binom{n}{i} a^i b^{n-i} $$
**Proof：**考虑使用数学归纳法：
当$n=1$时，$(a+b)^1=\binom{1}{0}a^0b^1+\binom{1}{1}a^1b^0=a+b$成立。
假设二项式定理在$n=m$时成立，当$n=m+1$时：
$$ \begin{aligned} (a + b)^{m+1} &= (a+b) \cdot (a+b)^m \\ &= a \cdot (a + b)^m + b \cdot (a + b)^m \\ &= a \cdot \sum_{i=0}^m \binom{m}{i} a^i b^{m-i} + b \cdot \sum_{i=0}^m \binom{m}{i} a^i b^{m-i} \\ &= \sum_{i=0}^m \binom{m}{i} (a^{i + 1} b^{m-i} + a^i b^{m - i + 1}) \\ &= \sum_{i=0}^{m+1} (\binom{m}{i-1} + \binom{m}{i}) a^i b^{m+1-i} \\ &= \sum_{i=0}^{m+1} \binom{m+1}{i} a^i b^{m+1-i} \end{aligned} $$
综上，由数学归纳法可知二项式定理成立。$\square$
定理：$\forall n, m \in \Z^+, p \in \mathbb{P}$：
$$ \begin{align} \binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \cdot \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \pmod p \end{align} $$
即取$n$和$m$的$p$进制展开，$n = \sum_{i = 0}^{k} n_i p^i, m = \sum_{i = 0}^{k} m_i p^i$，则：
$$ \begin{align} \binom{n}{m} \equiv \prod_{i = 0}^k \binom{n_i}{m_i} \pmod p \end{align} $$
**Proof：**只需证明式$(1)$即可。
引理：
$$ (1+x)^p \equiv 1+x^p \pmod p $$
Proof：
$$ (1+x)^p = \sum_{i=0}^p \binom{p}{i} x^i \\ \begin{aligned} \binom{p}{x} &= \frac{p!}{x!(p-x)!} = \frac{p (p-1)!}{x (x-1)!(p-x)!} \\ &= \frac{p}{x} \cdot \frac{(p-1)!}{(x-1)!(p-x)!} = \frac{p}{x} \binom{p-1}{x-1} \end{aligned} $$
当$0<x<p$时，$\binom{p}{x} \equiv p x^{-1}\binom{p-1}{x-1} \pmod p$，即$\binom{p}{x} \equiv 0 \pmod p$，故
$$ \begin{aligned} (1+x)^p &\equiv \sum_{i=0}^p \binom{p}{i} x^i &\pmod p \\ &\equiv \binom{p}{0} x^0 + \binom{p}{p} x^p &\pmod p \\ &\equiv 1 + x^p &\pmod p \end{aligned} $$
根据引理：
$$ \begin{aligned} (1+x)^n &\equiv \sum_{m=0}^n \binom{n}{m} x^m &\pmod p \\ (1+x)^n &\equiv (1+x)^{\lfloor \frac{n}{p} \rfloor \cdot p} \cdot (1+x)^{n \bmod p} &\pmod p \\ &\equiv ((1+x)^p)^{\lfloor \frac{n}{p} \rfloor} \cdot (1+x)^{n \bmod p} &\pmod p \\ &\equiv (1 + x^p)^{\lfloor \frac{n}{p} \rfloor} \cdot (1+x)^{n \bmod p} &\pmod p \\ &\equiv (\sum_{i=0}^{\lfloor \frac{n}{p} \rfloor} \binom{\lfloor \frac{n}{p} \rfloor}{i} x^{ip}) \cdot (\sum_{j=0}^{n \bmod p} \binom{n \bmod p}{j} x^j) &\pmod p \\ &\equiv \sum_{i=0}^{\lfloor \frac{n}{p} \rfloor} \sum_{j=0}^{n \bmod p} \binom{\lfloor \frac{n}{p} \rfloor}{i} \binom{n \bmod p}{j} x^{ip+j} &\pmod p \\ &\equiv \sum_{m=0}^n \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \binom{n \bmod p}{m \bmod p} x^m &\pmod p \\ \sum_{m=0}^n \binom{n}{m} x^m &\equiv \sum_{m=0}^n \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \binom{n \bmod p}{m \bmod p} x^m &\pmod p \end{aligned} $$
由$x$的任意性，对应系数相等，即$\binom{n}{m} \equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \binom{n \bmod p}{m \bmod p} \pmod p$。$\square$