问题及解答

引理. 考虑组合数 $C_n^{p^k}$.  设 $n=p^{\ell}m$, $k\leqslant\ell$ 且 $(p,m)=1$, 则

\[
p^{\ell-k}\bigr|C_n^{p^k},\quad\text{但}\quad p^{\ell-k+1}\not{\bigr|} C_n^{p^k}.
\]

参考[1]

[1] 聂灵沼、丁石孙 著 《代数学引论》

Pf.  

\[
C_{n}^{p^k}=\frac{n(n-1)(n-2)\cdots(n-p^k+1)}{p^k(p^k-1)(p^k-2)\cdots 2\cdot 1}=p^{\ell-k}m\cdot\frac{(n-1)(n-2)\cdots(n-p^k+1)}{(p^k-1)(p^k-2)\cdots 2\cdot 1}.
\]

记

\[
r=\frac{(n-1)(n-2)\cdots(n-p^k+1)}{(p^k-1)(p^k-2)\cdots 2\cdot 1}.
\]

可以看到 $n-i=p^{\ell}m-i$ 与 $p^k-i$ 在 $0 < i < p^k$ 时包含的 $p$ 的方幂是一样的. 事实上, 设 $i=p^t\cdot i_0$, 其中 $t < k$, $(p,i_0)=1$. 则

\[
\begin{aligned}
p^{\ell}m-i=p^{\ell}m-p^t\cdot i_0&=p^t(p^{\ell-t}m-i_0),\\
p^k-i=p^k-p^t\cdot i_0&=p^t(p^{k-t}-i_0).
\end{aligned}
\]

因此, $r$ 这个分数, 分子分母含有 $p$ 的个数相同, 在约分化简后, 

\[
r=\frac{(n-1)(n-2)\cdots(n-p^k+1)}{(p^k-1)(p^k-2)\cdots 2\cdot 1}
\]

成为一个不含因子 $p$ 的正整数. 于是 

\[
C_n^{p^k}=p^{\ell-k}mr
\]

可以被 $p^{\ell-k}$ 整除, 但不能被 $p^{\ell-k+1}$ 整除.