勒让德定理

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

背景

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

证明

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

$\begin{array}{cc}{\nu }_p(n!)& =n_1+2n_2+3n_3+...=\sum _{r\ge 1}r{n}_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{array}$

其中$N_k=n_k+n_{k+1}+...=\sum _{r\ge k}{n}_r$恰好是$2,3,\cdots ,n$这$n-1$个数中能被$p^k$除尽的数的个数，即$N_k=\lfloor \frac{n}{p^k}\rfloor$得证。

其它表達式

將$n$以$p$為基底寫做$n=n_{\ell }{p}^{\ell }+\cdots +n_{1}p+n_0$（進位制）

定義$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$

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

$\begin{array}{cc}{\nu }_p(n!)& =\sum _{i=1}^{\ell }\lfloor \frac{n}{p^i}\rfloor \\ & =\sum _{i=1}^{\ell }(n_{\ell }{p}^{\ell -i}+\cdots +n_{i+1}p+n_i)\\ & =\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 }(n_j{p}^j-n_j)\\ & =\frac{1}{p-1}(n-s_p(n)).\end{array}$