勒让德定理

勒让德定理指的是在正数n!的质因数分解中，質数p的指数记作\nu_p(n!)，则\nu_p(n!)=\sum_{k\ge 1} \left\lfloor{n \over p^k}\right\rfloor。有時這定理又以阿尔方·德·波利尼亚克為名而稱為德·波利尼亚克公式（de Polignac's formula）。

背景
勒让德定理是由法国数学家勒让德发现证明的。

证明
若把2,3,\cdots,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,\cdots,n这n-1个数中能被p^k除尽的数的个数，即N_k=\left\lfloor{n \over p^k}\right\rfloor得证。

其它表達式
將n以p為基底寫做n = n_\ell p^\ell + \cdots + n_1 p + n_0（進位制）

定義{\displaystyle s_{p}(n)=n_{0}+n_{1}+\cdots +n_{r}}是p底数的數位和，則

:\nu_p(n!) = \frac{n - s_p(n)}{p - 1}.

因此勒讓德定理可以用來證明庫默爾定理。

證明
n = n_\ell p^\ell + \cdots + n_1 p + n_0

\textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i

:
\begin{align}
\nu_p(n!)
&= \sum_{i=1}^{\ell} \left\lfloor \frac{n}{p^i} \right\rfloor \\
&= \sum_{i=1}^{\ell} \left(n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i\right) \\
&= \sum_{i=1}^{\ell} \sum_{j=i}^{\ell} n_j p^{j-i} \\
&= \sum_{j=1}^{\ell} \sum_{i=1}^{j} n_j p^{j-i} \\
&= \sum_{j=1}^{\ell} n_j \cdot \frac{p^j - 1}{p - 1} \\
&= \sum_{j=0}^{\ell} n_j \cdot \frac{p^j - 1}{p - 1} \\
&= \frac{1}{p - 1} \sum_{j=0}^{\ell} \left(n_j p^j - n_j\right) \\
&= \frac{1}{p - 1} \left(n - s_p(n)\right).
\end{align}