Legendre 定理

勒让德定理
术语名称	勒让德定理
英语名称	Legendre's formula

勒让德定理(Legendre's formula)是给出阶乘标准质因子分解的定理。

显然质数能整除阶乘当且仅当其不大于阶乘中最大的一个数，这个定理进一步给出了其指数的表达形式。

定理

对任意整数 [math]\displaystyle{ n }[/math] 的阶乘 [math]\displaystyle{ n! }[/math] ，记其分解式中质数 [math]\displaystyle{ p }[/math] 的指数为 [math]\displaystyle{ \nu_p(n!) }[/math] （即 [math]\displaystyle{ p }[/math] 进赋值函数），有

[math]\displaystyle{ \nu_p(n!) = \sum_{k=1}^\infty \left\lfloor \tfrac{n!}{p^k} \right\rfloor }[/math]

其中项 [math]\displaystyle{ \left\lfloor \tfrac{N}{M} \right\rfloor }[/math] 是这 [math]\displaystyle{ N }[/math] 个数中能被 [math]\displaystyle{ M }[/math] 整除的数的个数。 且由于 [math]\displaystyle{ n! }[/math] 有限，右侧的无穷求和实际上仅包含几个有效项，然后的都是 0 。

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解