勒讓德定理

在正數$n!$的質因數分解中，質數$p$的指數記作$\nu _{p}(n!)$，則$\nu _{p}(n!)=\sum _{k\geq 1}\left\lfloor {n \over p^{k}}\right\rfloor$。 physic,force use in science

背景

勒讓德定理是由法國數學家勒讓德發現證明的。

證明

若把$2,3,\cdots ,n$都分解成了標準分解式，則$\nu _{p}(n!)$就是這$n-1$個分解式中$p$的指數和。設其中$p$的指數為$r$的有$n_{r}$個($r\geq 1$)，則

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

其中$N_{k}=n_{k}+n_{k+1}+...=\sum _{r\geq 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{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}}$