勒讓德定理指的是在正數 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}\left\lfloor {n \over p^{k}}\right\rfloor } 。有時這定理又以阿爾方·德·波利尼亞克為名而稱為德·波利尼亞克公式(de Polignac's formula)。
勒讓德定理是由法國數學家勒讓德發現證明的。
若把 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}=\left\lfloor {n \over p^{k}}\right\rfloor } 得證。
將 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} 底數的數位和,則
因此勒讓德定理可以用來證明庫默爾定理。
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}}