勒让德定理在正数 n ! {\displaystyle n!} 的质因数分解中,质数 p {\displaystyle p} 的指数记作 ν p ( n ! ) {\displaystyle \nu _{p}(n!)} ,则 ν p ( n ! ) = ∑ k ≥ 1 [ n p k ] {\displaystyle \nu _{p}(n!)=\sum _{k\geq 1}[{n \over p^{k}}]} 。 目录 1 背景 2 证明 3 其它表达式 3.1 证明 背景 勒让德定理是由法国数学家勒让德发现证明的。 证明 若把 2 , 3 , ⋯ , n {\displaystyle 2,3,\cdots ,n} 都分解成了标准分解式,则 ν p ( n ! ) {\displaystyle \nu _{p}(n!)} 就是这 n − 1 {\displaystyle n-1} 个分解式中 p {\displaystyle p} 的指数和。设其中 p {\displaystyle p} 的指数为 r {\displaystyle r} 的有 n r {\displaystyle n_{r}} 个( r ≥ 1 {\displaystyle r\geq 1} ),则 ν p ( n ! ) = n 1 + 2 n 2 + 3 n 3 + . . . = ∑ r ≥ 1 r n r = ( n 1 + n 2 + n 3 + . . . ) + ( n 2 + n 3 + . . . ) + ( n 3 + . . . ) = N 1 + N 2 + N 3 + . . . = ∑ k ≥ 1 N k {\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}}} 其中 N k = n k + n k + 1 + . . . = ∑ r ≥ k n r {\displaystyle N_{k}=n_{k}+n_{k+1}+...=\sum _{r\geq k}n_{r}} 恰好是 2 , 3 , ⋯ , n {\displaystyle 2,3,\cdots ,n} 这 n − 1 {\displaystyle n-1} 个数中能被 p k {\displaystyle p^{k}} 除尽的数的个数,即 N k = [ n p k ] {\displaystyle N_{k}=[{n \over p^{k}}]} 得证。 其它表达式 将 n {\displaystyle n} 以 p {\displaystyle p} 为基底写做 n = n ℓ p ℓ + ⋯ + n 1 p + n 0 {\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}} (进位制) 定义 s p ( n ) = n 0 + n 1 + ⋯ + n r {\displaystyle {\displaystyle s_{p}(n)=n_{0}+n_{1}+\cdots +n_{r}}} 是 p {\displaystyle p} 底数的数位和,则 ν p ( n ! ) = n − s p ( n ) p − 1 . {\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.} 因此勒让德定理可以用来证明库默尔定理。 证明 n = n ℓ p ℓ + ⋯ + n 1 p + n 0 {\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}} ⌊ n p i ⌋ = n ℓ p ℓ − i + ⋯ + n i + 1 p + n i {\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}} ν p ( n ! ) = ∑ i = 1 ℓ ⌊ n p i ⌋ = ∑ i = 1 ℓ ( n ℓ p ℓ − i + ⋯ + n i + 1 p + n i ) = ∑ i = 1 ℓ ∑ j = i ℓ n j p j − i = ∑ j = 1 ℓ ∑ i = 1 j n j p j − i = ∑ j = 1 ℓ n j ⋅ p j − 1 p − 1 = ∑ j = 0 ℓ n j ⋅ p j − 1 p − 1 = 1 p − 1 ∑ j = 0 ℓ ( n j p j − n j ) = 1 p − 1 ( n − s p ( n ) ) . {\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}}}