~落書き帳「○△□」~
前回紹介した「ケンブリッヂの入試」の第3問に関連して、日本の大学入試問題から。
「p を素数、n を正の整数とするとき、(p^n)! は p で何回割り切れるか」
(2009 京都大学)
8年前の数楽の集いで、参加者の一人から質問があった問題だと記憶しています。
そのとき持参された問題集?には、
「1 から p^n までの p^n 個の整数の中で、p^k の倍数であるが p^(k+1) の倍数でないもの(1≦k≦n-1)と、p^n の倍数の個数の総和」
という、重複のないよう配慮する解答が載っていたように覚えています。
この問題は、「(p^n)! は p で…」という凝った作りが特徴的で、そこがかえって受験生を惑わしたかもしれません。
1 から p^n までの p^n 個の整数において、
(p^k の倍数の個数)= [(p^n)/(p^k)] ([ ] はガウス記号)
が成り立ちます。例えば「(p-1))×p^k」は、p^1、p^2、…、p^k の倍数ですから、
[(p^n)/(p^1)] 、[(p^n)/(p^2)] 、…、[(p^n)/(p^k)]
のそれぞれで1回ずつ、計 k 回カウントされます。しかし、これは重複ではありません。この数に含まれる素因数p の冪(個数)に一致します。
このことから、(p^n)! に含まれる素因数 p の個数は、
[(p^n)/(p^1)]+[(p^n)/(p^2)]+……+[(p^n)/(p^n)]
として求められます。すなわち、
p^(n-1)+p^(n-2)+……+1=(p^n-1)/(p-1)
これは、p^n)! が p で割り切れる回数に一致します。