查看“︁勒让德定理”︁的源代码

'''勒让德定理'''指的是在正数<math>n!</math>的[[质因数分解]]中，[[質数]]<math>p</math>的指数记作<math>\nu_p(n!)</math>，则<math>\nu_p(n!)=\sum_{k\ge 1} \left\lfloor{n \over p^k}\right\rfloor</math>。有時這定理又以阿尔方·德·波利尼亚克為名而稱為'''德·波利尼亚克公式'''（de Polignac's formula）。

== 背景 ==
'''勒让德定理'''是由[[法国]][[数学家]][[勒让德]]发现证明的。

== 证明 ==
若把<math>2,3,\cdots,n</math>都分解成了标准分解式，则<math>\nu_p(n!)</math>就是这<math>n-1</math>个分解式中<math>p</math>的[[冪運算|指数]]和。设其中<math>p</math>的[[冪運算|指数]]为<math>r</math>的有<math>n_r</math>个(<math>r\ge 1</math>)，则

<math>\begin{align}\nu_p(n!) &=n_1+2n_2+3n_3+...=\sum_{r\ge 1} rn_r\\
&=(n_1+n_2+n_3+...)+(n_2+n_3+...)+(n_3+...)=N_1+N_2+N_3+...=\sum_{k\ge 1} N_k\end{align}</math>

其中<math>N_k=n_k+n_{k+1}+...=\sum_{r\ge k} n_r</math>恰好是<math>2,3,\cdots,n</math>这<math>n-1</math>个数中能被<math>p^k</math>除尽的数的个数，即<math>N_k=\left\lfloor{n \over p^k}\right\rfloor</math>得证。

== 其它表達式 ==
將<math>n</math>以<math>p</math>為基底寫做<math>n = n_\ell p^\ell + \cdots + n_1 p + n_0</math>（[[進位制]]）

定義<math>{\displaystyle s_{p}(n)=n_{0}+n_{1}+\cdots +n_{r}}</math>是<math>p</math>[[底数 (进制)|底数]]的數位和，則

:<math>\nu_p(n!) = \frac{n - s_p(n)}{p - 1}.</math>

因此'''勒讓德定理'''可以用來證明[[庫默爾定理]]。

=== 證明 ===
<math>n = n_\ell p^\ell + \cdots + n_1 p + n_0</math>

<math>\textstyle \left\lfloor \frac{n}{p^i} \right\rfloor = n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i</math>

:<math>
\begin{align}
\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{align}
</math>

[[Category:数学定理|L]]
[[Category:数论]]