Legendreの公式 - ゆまるの数学日記

Legendreの公式（Legendreの定理）*1は，数論の基本的な公式（定理）です．チェビシェフの定理（ $n$ と $2n$ の間に素数が存在する）などの証明でも登場するような公式ですので，高校生でも覚えておくといろいろ得をすると思われます．

Legendreの公式

自然数 $n$ に対して， $n$ に含まれる素因数 $p$ の個数（ $n$ を素因数分解したときの $p$ の累乗指数）を $\mathrm{ord}_p(n)$ とすれば，

$\displaystyle \mathrm{ord}_p(n!) = \sum_{i=1}^{\infty} \left[ \frac{n}{p^i} \right] = \sum_{i=1}^{[\log_{p}n]} \left[ \frac{n}{p^i} \right]$

が成り立つ．ここで $[ x ]$ は $x$ を超えない最大の整数を表すものとする．

証明*2

$n$ までの $p$ の倍数は $\displaystyle \left[ \frac{n}{p} \right]$ 個である．（ $p$ の倍数は， $p$ から $p$ 個おきに出てくることに注意せよ）
また， $n$ までの $p^2$ の倍数は $\displaystyle \left[ \frac{n}{p^2} \right]$ 個である．
これを繰り返すことで， $n!$ に含まれる素因数 $p$ の個数を数えることができ，それは $\displaystyle \sum_{i=1}^{\infty} \left[ \frac{n}{p^i} \right]$ である．
また， $i \gt \log_{p} n$ のとき $\displaystyle \left[ \frac{n}{p^i} \right] = 0$ であるから， $\displaystyle \sum_{i=1}^{\infty} \left[ \frac{n}{p^i} \right] = \sum_{i=1}^{[\log_{p}n]} \left[ \frac{n}{p^i} \right]$ である．Q.E.D.

大学入試問題

問題． $p$ を素数， $n$ を正の整数とするとき， $(p^n)!$ は $p$ で何回割り切れるか．

（'09 京都大学文甲共通）

解答

求める数は $\mathrm{ord}_p((p^n)!)$ である．Legendreの定理より，

$\begin{align} \displaystyle \mathrm{ord}_p((p^n)!) &= \sum_{i=1}^{[\log_{p}p^n]} \left[ \frac{p^n}{p^i} \right] = \sum_{i=1}^{n} p^{n-i} \\ &= p^{n-1} + p^{n-2} + \cdots + p + 1 = \frac{p^n - 1}{p - 1} \end{align}$

素数の無限性の証明

素数の無限性の証明は山ほどあるが，Legendreの定理を用いて証明することもできます．すごい！！

素数の無限性の証明

$\begin{align} \displaystyle \mathrm{ord}_p(n!) &= \sum_{i=1}^{\infty} \left[ \frac{n}{p^i} \right] \leq \sum_{i=1}^{\infty} \frac{n}{p^i} = \frac{n}{p} \cdot \frac{1}{1-\frac{1}{p}} \\ &= \frac{n}{p-1} \leq n \end{align}$