Legendre 定理
| 勒让德定理 | |
|---|---|
| 术语名称 | 勒让德定理 |
| 英语名称 | Legendre's formula |
Legendre 定理(Legendre's formula)是给出阶乘标准质因子分解的定理。
显然质数 [math]\displaystyle{ p }[/math] 能整除阶乘 [math]\displaystyle{ n! }[/math] 当且仅当 [math]\displaystyle{ p\leq n }[/math] ，而 Legendre 定理在此基础上进一步给出了其指数的表达形式。
定理
对任意整数 [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{ n }[/math] 有限，随着 [math]\displaystyle{ p^k }[/math] 的增大，直到 [math]\displaystyle{ k \gt \log_p n }[/math] 后就会超过 [math]\displaystyle{ n }[/math] ，因此右侧的无穷求和实际上仅包含 [math]\displaystyle{ \lfloor\log_p n\rfloor }[/math] 个有效项，后续的都是 0 。