数学A 整数問題 問題 47 解説

方針・初手

階乗 $(p^n)!$ の中に含まれる素因数 $p$ の個数を数えればよい。

$1,2,\dots,p^n$ のうち、$p$ の倍数はそれぞれ少なくとも1個の $p$ を含み、$p^2$ の倍数はさらにもう1個、というように重複して数える。したがって、$p,p^2,\dots,p^n$ の倍数の個数を合計する。

解法1

$(p^n)!$ に含まれる素因数 $p$ の個数を $v_p((p^n)!)$ とおく。

$1$ から $p^n$ までの整数のうち、$p$ の倍数の個数は

$$ \left\lfloor \frac{p^n}{p} \right\rfloor=p^{n-1} $$

である。

この中で $p^2$ の倍数は、すでに $p$ の倍数として1回数えられているが、実際には少なくとも2個の $p$ を含むので、さらに1回数える必要がある。その個数は

$$ \left\lfloor \frac{p^n}{p^2} \right\rfloor=p^{n-2} $$

である。

同様に、$p^k$ の倍数の個数は

$$ \left\lfloor \frac{p^n}{p^k} \right\rfloor=p^{n-k} $$

である。ここで $k=1,2,\dots,n$ までを考えればよい。$k>n$ では $p^k>p^n$ となり、$p^k$ の倍数は存在しない。

よって、

$$ \begin{aligned} v_p((p^n)!) &=\left\lfloor \frac{p^n}{p} \right\rfloor +\left\lfloor \frac{p^n}{p^2} \right\rfloor +\cdots +\left\lfloor \frac{p^n}{p^n} \right\rfloor\\ &=p^{n-1}+p^{n-2}+\cdots+p+1. \end{aligned} $$

これは初項 $1$、公比 $p$、項数 $n$ の等比数列の和であるから、

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

である。

したがって、$(p^n)!$ は $p$ で

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

回割り切れる。

解説

階乗が素数 $p$ で何回割り切れるかを問う問題では、$p$ の倍数だけでなく、$p^2,p^3,\dots$ の倍数を重ねて数えることが重要である。

例えば $p^2$ の倍数は $p$ を2個以上含むため、$p$ の倍数として1回数えただけでは不足する。この不足分を補うために、$p^2$ の倍数、$p^3$ の倍数、という順に加えていく。

この考え方により、

$$ v_p(m!)=\left\lfloor \frac{m}{p} \right\rfloor+\left\lfloor \frac{m}{p^2} \right\rfloor+\left\lfloor \frac{m}{p^3} \right\rfloor+\cdots $$

という形になる。今回は $m=p^n$ なので、各項がきれいに $p^{n-1},p^{n-2},\dots,1$ となる。

答え

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