京都大学 2009年度 前期日程 第2次学力試験（文系・数学理系甲共通）理系（甲）数学 第5問

$(p^n)!$とは $1\cdot 2\cdot 3\cdots p^n$ である。この積を素因数分解したとき，素因数$p$が全部で何個現れるかを数えれば，$(p^n)!$が$p$で割り切れる回数が分かる。

まず，$1,2,\dots ,p^n$の中で$p$の倍数は $${\displaystyle \frac{p^n}{p}}=p^{n-1}$$ 個ある。これらの数は，少なくとも1個の$p$を因数にもつ。したがって，この段階で$p^{n-1}$個分の$p$を数えたことになる。

ただし，これだけでは足りない。例えば$p^2$の倍数は $p^2\cdot m$ の形をしているので，すでに$p$の倍数として1個分は数えられているが，さらにもう1個分の$p$を余分にもっている。したがって，$p^2$の倍数の個数を追加で数える必要がある。その個数は $${\displaystyle \frac{p^n}{p^2}}=p^{n-2}$$ 個である。

同様に，$p^3$の倍数は，$p$の倍数として1回，$p^2$の倍数としてもう1回数えられたあと，さらに追加でもう1個分の$p$をもつ。その追加分は $${\displaystyle \frac{p^n}{p^3}}=p^{n-3}$$ 個である。

このように考えると，$p^r$の倍数は，$p$を少なくとも$r$個含む数に対応しており，$r$個目の$p$を数えるために $${\displaystyle \frac{p^n}{p^r}}=p^{n-r}$$ 個を加えればよい。ただし$r=1,2,\dots ,n$である。$r=n$のときは$p^n$の倍数がちょうど1個あり，それより高い$p^{n+1}$の倍数は$p^n$以下には存在しない。

したがって，$(p^n)!$に含まれる素因数$p$の個数は $p^{n-1}+p^{n-2}+\cdots +p+1$ である。これは初項1，公比$p$，項数$n$の等比数列の和と見れば $$1+p+p^2+\cdots +p^{n-1}={\displaystyle \frac{p^n-1}{p-1}}$$ である。よって求める回数は ${\displaystyle \frac{p^n-1}{p-1}}$ である。

$e_n$ を $(p^n)!$ に含まれる素因数 $p$ の個数とする。積のうち $p$ の倍数だけを取り出すと、各倍数からまず $p$ が1個ずつ現れ、残った積は $(p^{n-1})!$ になる。これにより $e_n=p^{n-1}+e_{n-1}$ を作り、初期値 $e_1=1$ から解く。

$e_n$ を $(p^n)!$ の素因数分解に現れる $p$ の個数とする。
$1,2,\dots ,p^n$ のうち $p$ を因数にもつ項だけを集めると$$p\cdot 2p\cdot 3p\cdots p^{n-1}p=p^{p^{n-1}}(p^{n-1})!$$となる。したがって、$p$ の倍数それぞれから取り出した $p^{n-1}$ 個分と、
残った $(p^{n-1})!$ に含まれる分を合わせて$$e_n=p^{n-1}+e_{n-1}$$である。

$e_1=1$ なので、この漸化式を順に用いると$$\begin{array}{rl}{\displaystyle e_n}& {\displaystyle =p^{n-1}+p^{n-2}+\cdots +p+1}\\ {\displaystyle }& {\displaystyle ={\displaystyle \frac{p^n-1}{p-1}}\mathrm{.}}\end{array}$$よって、$(p^n)!$ は $p$ で$${\displaystyle \frac{p^n-1}{p-1}}\text{ 回}$$割り切れる。