\(C^m_n \equiv C^{m/p} _ {n/p} * C^{m \ mod \ p} _ {n \ mod \ p}\)
首先，我们可以知道如下定理
我们令 \(n = ap + b\),\(m = cp + d\)
则由二项式定理得 \((1+x)^n \equiv \Sigma_{i = 0}^nC^i_nx^i(mod \ p)\)---------(1)
由 \(n = ap + b\) 可知
\((1+x)^n \equiv (1+x)^{ap+b}\)
\((1+x)^n \equiv ((1+x)^{p})^a * (1+x)^b\)
由引理二可得
\((1+x)^n \equiv (1+x^p)^a * (1+x)^b\)
据二项式定理得
\((1+x^p)^a \equiv \Sigma_{i = 0}^aC^i_ax^{i * p}\)
\((1+x)^b \equiv \Sigma_{j=0}^bC^j_bx^j\)
则
\((1+x)^n \equiv \Sigma_{i = 0}^aC^i_ax^{i * p} * \Sigma_{j=0}^bC^j_bx^j\)
由于
\((1+x)^n \equiv \Sigma_{i = 0}^nC^i_nx^i(mod \ p)\)
则
\(\Sigma_{i = 0}^nC^i_nx^i \equiv \Sigma_{i = 0}^aC^i_ax^{i * p} * \Sigma_{j=0}^bC^j_bx^j\)
由(1)可知在 \(i=m\) 时 \(x^m\) 的系数为 \(C^m_n\)
在(2)中 \(x^m=x^{cp+d}=x^{cp} * x ^ {d}\)
带入可得
\(C^m_nx^m \equiv C^c_ax^{cp} * C^d_bx^d\)
\(C^m_nx^m \equiv C^c_aC^d_bx^{cp} * x^d\)
显然
\(C^m_n \equiv C^c_aC^d_b(mod \ p)\)
即 \(C^m_n \equiv C^{m/p} _ {n/p} * C^{m \ mod \ p} _ {n \ mod \ p}\)