問題.
方針．
解答例．
普通に解いてみると
は素数であるから，
から
のそれぞれの自然数が
で割り切れる回数を数え上げればいい．
で
回ちょうど割り切れる数の個数は，
で割り切れて
で割り切れない数と考えることで，
\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*}
となります．
としては
の範囲で考えればいいので，
を
が割り切る回数は，
\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)というものが存在します．これは，自然数 
と素数 
に対して， を が割り切る回数を 
と表すこととします．このとき， \begin{align*} \nu_p(n!) &= \sum_{i=1}^\infty \left\lfloor\frac{n}{p^i}\right\rfloor \end{align*}
右辺は無限和になっていますが，
が十分大きくなると 
はゼロとなるので，実質的には有限和です．
この公式の右辺の各項 は， 以下で，
で割り切れる数，つまり で 回以上割り切れる数の個数を表しています．
これを 
として足し合わせていくと，
︙ で 
回だけ割り切れる数は 
の 回数えられる
︙
というようになるので，上手く で割り切れる回数を数えられていることがわかります．
では，今回の問題にルジャンドルの公式を使ってみましょう．
ルジャンドルの公式を使うと...
求めたいものは，上の記号を用いれば，\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*}
となり，ちゃんと同じ答えになります．
