勒让德公式与Kummer定理

设$p$为素数，我们以符号$p^{a}||n$表达$p^{a}||n$而$p^{a+1}\nmid n$.

代数学讲义中的一道习题就是证明勒让德公式：

设$p$为素数.对所有非零整数$m$取唯一的$v_{p}(m)\in \mathbb{Z}_{\geq 0}$使得$p^{v_{p}(m)}||m$.
(1)设$n\in \mathbb{Z}_{\geq 0}$.证明$v_{p}(n!)=\sum\limits_{ k = 1 }^\infty \left\lfloor \frac{n}{p^{k}} \right\rfloor$.
(2)作$p$进制展开$n=a_{0}+a_{1}p+\dots+a_{r}p^{r}$.基于(1),证明：$v_{p}(n!)=\frac{n-\sum\limits_{ i=0 }^ra_{i}}{p-1}$.

证明：(1)$1,2,3,\dots,n$中，
能被$p$整除的有$\left\lfloor \frac{n}{p} \right\rfloor$个，为$v_{p}(n!)$贡献$1$
能被$p^{2}$整除的有$\left\lfloor \frac{n}{p^{2}} \right\rfloor$个，为$v_{p}(n!)$贡献$2$
$\dots$
能被$p^{k}$整除的有$\left\lfloor \frac{n}{p^{k}} \right\rfloor$个，为$v_{p}(n!)$贡献$k$
但被$p^{k}$整除的，同时也被$p^{k-1},p^{k-2},\dots,p^{2},p$整除，
所以每部分只用计算$1$的贡献值，即证得(1).
(2)在(1)的基础上，这是显然的：

$$\begin{align} v_{p}(n!) & =\sum\limits_{ k=1 }^\infty \left\lfloor \frac{\sum\limits_{ i=0}^r a_{i}p^{i} }{p^{k}} \right\rfloor \\ & =\sum\limits_{ i=0 }^{r} \sum_{k=1}^{\infty}\left\lfloor \frac{a_{i}p^{i}}{p^{k}} \right\rfloor \\ & =\sum_{i=0}^{r} \sum_{k=1}^{\infty} a_{i}\frac{p^{i}-1}{p-1} \\ & =\frac{\sum_{i=0}^{r}a_{i}p^{i}-\sum_{i=0}^{r}a_{i} }{p-1} \\ & =\frac{n-\sum_{i=0}^{r}a_{i} }{p-1} \end{align}$$

Kummer定理

$v_{p}(C_{n+m}^)$等于$n$和$m$在$p$进制加法中进位的次数。

简要推导：

$$\begin{align} v_{p}(C_{n+m}^{m}) & =v_{p}((n+m)!)-v_{p}(m!)-v_{p}(n!) \\ & =\sum_{i=1}^{\infty} \left\lfloor \frac{n+m}{p^{i}} \right\rfloor - \sum_{i=1}^{\infty} \left\lfloor \frac{m}{p^{i}} \right\rfloor-\sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^{i}} \right\rfloor \\ & =\sum_{i=1}^{\infty} \left( \left\lfloor \frac{n+m}{p^{i}} \right\rfloor-\left\lfloor \frac{m}{p^{i}} \right\rfloor -\left\lfloor \frac{n}{p^{i}} \right\rfloor \right) \end{align}$$

对于每一个$i$,$\left\lfloor \frac{n+m}{p^{i}} \right\rfloor-\left\lfloor \frac{m}{p^{i}} \right\rfloor -\left\lfloor \frac{n}{p^{i}} \right\rfloor$在第$i$位进位时为$1$，否则为$0$。

推论：$v_{p}(C_{p^{m}}^)=m-v_{p}(k)$

简单应用
$(x-1)^{2025}$的展开式中，系数为偶数的有多少项。

由二项式定理，即求满足$C_{2025}^{x}\equiv 0\pmod{2}$的个数，
先求满足$C_{2025}^{x}\equiv 1\pmod{2}$的个数，即$v_{2}(C_{2025}^{x})=0$
故二进制中$2017$的某位为$0$，那么$x$这位也必须为$0$；为$1$时$x$无限制。
又$(2017)_{10}=(11111101001)_{2}$，共$8$个$1$，答案为$2026-2^{8}=1770$