京都大学 2009年 文系 第5問（甲） 解説

方針・初手

階乗に含まれる素因数の個数を求める典型問題です。$1$ から $p^n$ までの整数のうち、$p$ の倍数、$p^2$ の倍数、…、$p^n$ の倍数がそれぞれ何個あるかを数え上げ、それらの総和を計算します。最後に等比数列の和の公式を用いて結果を簡潔にまとめます。

解法1

$(p^n)! = 1 \cdot 2 \cdot 3 \cdots p^n$ である。$(p^n)!$ が素数 $p$ で割り切れる回数は、この積に含まれる素因数 $p$ の個数に等しい。

$1$ から $p^n$ までの自然数のうち、$p$ の累乗の倍数がいくつあるかを考える。$k$ を $1 \leqq k \leqq n$ を満たす整数とすると、$1$ から $p^n$ までの自然数の中に $p^k$ の倍数は

$$ \frac{p^n}{p^k} = p^{n-k} \text{ (個)} $$

存在する。

各自然数が持つ素因数 $p$ の個数の総和は、「$p$ の倍数の個数」「$p^2$ の倍数の個数」……「$p^n$ の倍数の個数」をすべて足し合わせることで求められる（ルジャンドルの定理の考え方）。したがって、求める回数 $N$ は、

$$ N = p^{n-1} + p^{n-2} + \cdots + p^1 + p^0 $$

となる。

この式は、初項 $1$、公比 $p$、項数 $n$ の等比数列の和を表している。$p$ は素数であるから $p \geqq 2$ であり、$p - 1 \neq 0$ であるため、等比数列の和の公式より

$$ N = \frac{p^n - 1}{p - 1} $$

と計算できる。

解説

「階乗の素因数の個数」を求める定石を文字式で一般化した問題です。例えばある数が $p^3$ の倍数であるとき、その数は素因数 $p$ を3個持ちますが、これを「$p$ の倍数として1回、$p^2$ の倍数として1回、$p^3$ の倍数として1回」とカウントすることで、数え漏らしや重複を防ぐことができます。具体例として $p=2, n=3$（$8!$ が $2$ で何回割り切れるか）などを想定して検算すると、$\frac{2^3 - 1}{2 - 1} = 7$ となり、実際の $4+2+1=7$ と一致することが確認できます。

答え

$$ \frac{p^n - 1}{p - 1} \text{ 回} $$