皆さん, こんにちは. 今回は, ルジャンドルの定理とその証明を述べます.
準備
実数 \(x\) に対して, \(\lfloor x \rfloor\) で \(x\) 以下の最大の整数を表します. 例えば, \(\lfloor 3.14 \rfloor = 3, \lfloor 2 \rfloor = 2\) です. 関数
\[
\lfloor \bullet \rfloor: \mathbb{R} \to \mathbb{Z}
\] を床関数といいます.
ここで, \(a\) および \(n\) を正の整数とすると, \(1\) 以上 \(n\) 以下の \(a\) の倍数の個数は \(\left\lfloor\frac{n}{a}\right\rfloor\) です. なぜなら, \(1\) 以上 \(n\) 以下の \(a\) の倍数をすべて列挙すると
\[
1a, 2a, \cdots, \left\lfloor\frac{n}{a}\right\rfloor a
\] となるからです. ちなみに,
\[
\left( \left\lfloor\frac{n}{a}\right\rfloor + 1 \right) a > \frac{n}{a} a = n
\] なので, \(\left( \left\lfloor\frac{n}{a}\right\rfloor + 1 \right) a\) は \(n\) より大きくなってしまうことに注意してください.
定理（ルジャンドルの定理）
\(n\) を正の整数, \(p\) を素数とする. このとき, \(n!\) が \(p\) で割り切れる回数は
\[
\sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \left\lfloor \frac{n}{p^1} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots
\] である.（無限和の形をしているが, 実質的に有限和である. ）
証明
正の整数 \(m\) に対して, \(m\) は素数 \(p\) で \(v_p(m)\) 回割り切れるものとします. つまり, 次の性質を満たす負でない整数 \(k\) がただひとつ存在するので, それを \(v_p(m)\) とおきます.
【性質】\(m\) は \(p^k\) で割り切れるが, \(p^{k + 1}\) では割り切れない.
また, 負でない整数 \(k\) と正の整数 \(a\) に対して, \(f_p(a, k)\) を次で定めます.
\[
f_p(a, k) = \begin{cases}
1, & a \ は \ p^k \ で割り切れる, \\
0, & a \ は \ p^k \ で割り切れない.
\end{cases}
\] ここで, 負でない整数 \(k\) と正の整数 \(l\) に対して, 次が成り立ちます.
\[
k \leq v_p(l) \Longleftrightarrow l \ は \ p^k \ で割り切れる \Longleftrightarrow f_p(l, k) = 1.
\] したがって, 正の整数 \(l\) に対して,
\begin{align}
\sum_{k = 1}^{\infty} f_p(l, k) &= \# \{k \in \mathbb{Z}_{>0} \mid f_p(l, k) = 1 \} \\
&= \# \{k \in \mathbb{Z}_{>0} \mid k \leq v_p(l) \} \\
&= v_p(l).
\end{align} また, 正の整数 \(k\) に対して,
\begin{align}
\sum_{l = 1}^{n} f_p(l, k) &= \# \{ l \in \mathbb{Z} \mid 1 \leq l \leq n \ かつ \ l \ は \ p^k \ で割り切れる \} \\
&= \left\lfloor \frac{n}{p^k} \right\rfloor.
\end{align} ゆえに,
\begin{align}
v_p(n!) &= \sum_{l = 1}^{n} v_p(l) \\
&= \sum_{l = 1}^{n} \sum_{k = 1}^{\infty} f_p(l, k) \\
&= \sum_{k = 1}^{\infty} \sum_{l = 1}^{n} f_p(l, k) \\
&= \sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor.
\end{align} 以上により, 題意は示されました.
コメント