Fussy's Diary

行き詰まった時についつい挑戦したくなります。おかげで本題の方がなかなか進みません。しばらくは封印したいと思います。

■ p を素数、n を正の整数とするとき、( pⁿ )! は p で何回割り切れるか (09京都・文理)

1 から pⁿ までの数の中に、p の倍数は p^n-1 個ある。なぜなら、p の倍数は p 個おきに見つかるから。同様に考えれば、p² の倍数は p^n-2 個ある。これを続けると、最終的には pⁿ の倍数として pⁿ そのものが 1 個だけ見つかる。

p² の倍数は p の倍数でもあるので、1 個分が p の倍数の個数分に含まれる。p² の倍数 1 個に対しては 2 個の p が含まれるので、残りは p^n-2 個になる。p³ の倍数は p² と p の倍数でもあり、すでに 2 個分はカウントされているので、残りは p^n-3 個。

従って、Σ{0→n-1}( p^k ) を求めれば 1 から pⁿ までの数の中に含まれる p の個数が得られる。これは、(pⁿ)! に含まれる p の個数そのものである。

パズルみたいで解いていて結構楽しかったです。小さな数で実際に試してみるのが理解する一番の近道でしょうか。