勒让德公式

**第1步:将 $v_p(n!)$ 写成对各因子的求和。** 由定义 $n! = 1\cdot 2\cdots n$,故 $v_p(n!) = \sum_{k=1}^{n} v_p(k)$,即从 $1$ 到 $n$ 每个整数的 $p$进赋值之和。

**第2步:将每个 $v_p(k)$ 改写为计数。** 对每个 $k$,$v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$(用艾弗森记号,真为 $1$,假为 $0$),因为 $k$ 恰好对 $v_p(k)$ 个 $i$ 值(即 $i=1,\dots,v_p(k)$)能被 $p^i$ 整除。

第3步:交换求和顺序。 代入得 $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$,交换(有限从而合理的)双重求和。

**第4步:直接计数 $p^i$ 的倍数。** 内层和 $\sum_{k=1}^n [p^i \mid k]$ 计数 $1$ 到 $n$ 中有多少整数是 $p^i$ 的倍数,恰为 $\left\lfloor \frac{n}{p^i} \right\rfloor$(这些倍数为 $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$)。

第5步:结论。 代回得 $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$,由于一旦 $p^i > n$ 就有 $\lfloor n/p^i \rfloor = 0$,故该和有限,证明完成。