n!中素因子的数量

abababa

$n\ge2$，在$n!$的标准分解中，素因子$p$的指数$\alpha$为
\[\alpha=\sum_{i=1}^{\infty}[\frac{n}{p^i}]\]

其中$[x]$表示不超过$x$的最大整数。

这个我用特殊的数字是能理解，比如 $n=10$，然后$10!$中$2$的指数就只能从$2,4,6,8,10$里出，共$5$个，就是$[\frac{10}{2^1}]$，然后这些都约掉一个$2$，剩下的就是$1,2,3,4,5$，只有$2,4$还能出因子$2$，共$2$个，就是$[\frac{10}{2^2}]$，这些再约掉一个$2$得$1,2$，就只有$2$还能出因子$2$，共$1$个，就是$[\frac{10}{2^3}]$，然后就不能出$2$了，结束。这样加起来就是那个表达式。但对一般的$n,p$，要怎么用数学的方式证明它呢？

kuing

想起了这帖 forum.php?mod=viewthread&tid=3002

tommywong

Legendre's formula

Since $n!$ is the product of the integers 1 through n, we obtain at least one factor of p in $n!$ for each multiple of p in $\{1, 2, \dots, n\}$, of which there are $\textstyle \left\lfloor \frac{n}{p} \right\rfloor$.  Each multiple of $p^2$ contributes an additional factor of p, each multiple of $p^3$ contributes yet another factor of p, etc.  Adding up the number of these factors gives the infinite sum for $\nu_p(n!)$.

tommywong

維基中文版有另一版本的證明

若把2,3,...,n都分解成了标准分解式，则$\nu_p(n!)$就是这n-1个分解式中p的指数和.设其中p的指数为r的有$n_r$个($r\ge 1$)，则

$\begin{align*}\nu_p(n!) &=n_1+2n_2+3n_3+...=\sum_{r\ge 1} rn_r\\
&=(n_1+n_2+n_3+...)+(n_2+n_3+...)+(n_3+...)=N_1+N_2+N_3+...=\sum_{k\ge 1} N_k\end{align*}$

其中$N_k=n_k+n_{k+1}+...=\sum_{r\ge k} n_r$恰好是2,3,...,n这n-1个数中能被$p^k$除尽的数的个数，即$N_k=[{n \over p^k}]$得证。

abababa

回复 3# tommywong

原来如此，这个证明懂了。这还是个有名字的定理啊。

回复 2# kuing

就是在算这种末尾有几个零的题时用到这个定理了。

hbghlyj

Legendre公式
\[
e_p(n!) = \frac{n - S_p(n)}{p-1}
\]
其中 $p$ 是质数，$e_p(n!)$ 表示 $p$ 在 $n!$ 的质因数分解中的指数，而 $S_p(n)$ 表示 $n$ 用 $p$ 进制表示时的数字和。
设 $n$ 的 $p$ 进制表示为
$$
e_xe_{x-1}e_{x-2}\dots e_0
$$
那么，$\left\lfloor \frac{n}{p^i}\right\rfloor$ 的 $p$ 进制表示为
$$
e_xe_{x-1}\dots e_{i}
$$
$e_p(n!)=\sum_{i=1}^{\infty}\lfloor\frac{n}{p^i}\rfloor$代入得：
\begin{align*}
\sum_{j=1}^{x} e_j\cdot(p^{j-1}+p^{j-2}+\cdots +1)
&= \sum_{j=1}^{x} e_j \cdot \frac{p^j - 1}{p-1} \\
&= \frac{\sum_{j=1}^{x} e_jp^j - \sum_{j=1}^{x} e_j}{p-1} \\
&= \frac{(n-e_0) - (S_p(n)-e_0)}{p-1} \\
&= \frac{n - S_p(n)}{p-1}.
\end{align*}