勒让德定理

勒让德定理指的是在正数${\displaystyle n!}$的质因数分解中，质数${\displaystyle p}$的指数记作${\displaystyle \nu _{p}(n!)}$，则${\displaystyle \nu _{p}(n!)=\sum _{k\geq 1}\left\lfloor {n \over p^{k}}\right\rfloor }$。有时这定理又以阿尔方·德·波利尼亚克为名而称为德·波利尼亚克公式（de Polignac's formula）。

背景

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

证明

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

${\displaystyle {\begin{aligned}\nu _{p}(n!)&=n_{1}+2n_{2}+3n_{3}+...=\sum _{r\geq 1}rn_{r}\\&=(n_{1}+n_{2}+n_{3}+...)+(n_{2}+n_{3}+...)+(n_{3}+...)=N_{1}+N_{2}+N_{3}+...=\sum _{k\geq 1}N_{k}\end{aligned}}}$

其中${\displaystyle N_{k}=n_{k}+n_{k+1}+...=\sum _{r\geq k}n_{r}}$恰好是${\displaystyle 2,3,\cdots ,n}$这${\displaystyle n-1}$个数中能被${\displaystyle p^{k}}$除尽的数的个数，即${\displaystyle N_{k}=\left\lfloor {n \over p^{k}}\right\rfloor }$得证。

其它表达式

将${\displaystyle n}$以${\displaystyle p}$为基底写做${\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}}$（进位制）

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

${\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.}$

因此勒让德定理可以用来证明库默尔定理。

证明

${\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}}$

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

${\displaystyle {\begin{aligned}\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{aligned}}}$