京大2009年度理系[甲]第5問〜ルジャンドルの公式〜

この記事の所要時間: 345

問題.

\(p\) を素数,\(n\) を正の整数とするとき,\((p^n)!\) は \(p\) で何回割り切れるか.

方針.

\(p\) が素数なので,\((p^n)!\) を \(p\) が割り切る回数は,\(1, 2, \ldots, p^n\) を \(p\) が割り切る回数を足し合わせればいいことがわかります.

解答例.

普通に解いてみると

\((p^n)!\) を \(p\) が割り切る回数をどのように数え上げるかが問題です.

\(p\) は素数であるから,\(1\) から \(p^n\) のそれぞれの自然数が \(p\) で割り切れる回数を数え上げればいい.

\(p\) で \(i\) 回ちょうど割り切れる数の個数は,\(p^i\) で割り切れて \(p^{i+1}\) で割り切れない数と考えることで,
\begin{align*}
\left\lfloor\frac{p^n}{p^i}\right\rfloor-\left\lfloor\frac{p^n}{p^{i+1}}\right\rfloor &= p^{n-i}-p^{n-i-1}.
\end{align*}

となります.

\(i\) としては \(1\leq i\leq n\) の範囲で考えればいいので,

\((p^n)!\) を \(p\) が割り切る回数は,

\begin{align*}
1\cdot(p^{n-1}-p^{n-2})&+2\cdot(p^{n-2}-p^{n-3})+\cdots+(n-1)\cdot(p-1)+n\cdot 1 \\ &=p^{n-1}+p^{n-2}+\cdots+p+1\\
&= \frac{p^n-1}{p-1}
\end{align*}

となる.

ルジャンドルの公式とは…

この問題の背景には,ルジャンドルの公式(Legendre)というものが存在します.これは,\(n!\) を素数 \(p\) が割り切る回数を求める公式です.

自然数 \(n\) と素数 \(p\) に対して,\(n\) を \(p\) が割り切る回数を \(\nu_p(n)\) と表すこととします.このとき, \begin{align*} \nu_p(n!) &= \sum_{i=1}^\infty \left\lfloor\frac{n}{p^i}\right\rfloor \end{align*}
右辺は無限和になっていますが,\(i\) が十分大きくなると \(\left\lfloor\frac{n}{p^i}\right\rfloor\) はゼロとなるので,実質的には有限和です.

この公式の右辺の各項 \(\left\lfloor\frac{n}{p^i}\right\rfloor\) は,\(n\) 以下で,\(p^i\) で割り切れる数,つまり \(p\) で \(i\) 回以上割り切れる数の個数を表しています.
これを \(i=1,2,\ldots\) として足し合わせていくと,
\(p\) で 1 回だけ割り切れる数は \(i=1\) のときだけ数えられる
\(p\) で 2 回だけ割り切れる数は \(i=1, 2\) の 2 回数えられる

\(p\) で 3 回だけ割り切れる数は \(i=1, 2, 3\) の 3 回数えられる
     ︙

\(p\) で \(k\) 回だけ割り切れる数は \(i=1, 2, \ldots, k\) の \(k\) 回数えられる

     ︙
というようになるので,上手く \(p\) で割り切れる回数を数えられていることがわかります.
では,今回の問題にルジャンドルの公式を使ってみましょう.

ルジャンドルの公式を使うと…

求めたいものは,上の記号を用いれば,\(\nu_p((p^n)!)\) なので,ルジャンドルの公式に当てはめることで

\begin{align*}
\nu_p((p^n)!) &= \sum_{i=1}^\infty \left\lfloor\frac{p^n}{p^i}\right\rfloor\\
&= \sum_{i=1}^n p^{n-i}\\
&= \sum_{i=0}^{n-1} p^i\\
&= \frac{p^n-1}{p-1}.
\end{align*}

となり,ちゃんと同じ答えになります.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加