Evolton

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

p を素数,n を正の整数とするとき,
(pn)! は p で何回割り切れるか.

難易度4/ 10計算量3/ 10目安10分

整数 素因数分解、数え上げ、和の計算

方針

(pn)!に含まれる素因数pの個数を,1,2,…,pnの中にあるp,p2,…,pnの倍数の個数として重複込みで数える。pの倍数は1回分,p2の倍数は追加でもう1回分,というように数えると,合計はpn−1+pn−2+⋯+1になる。最後に等比数列の和で閉じる。

解答

(pn)!とは 1⋅2⋅3⋯pn である。この積を素因数分解したとき,素因数pが全部で何個現れるかを数えれば,(pn)!がpで割り切れる回数が分かる。

まず,1,2,…,pnの中でpの倍数は pnp=pn−1 個ある。これらの数は,少なくとも1個のpを因数にもつ。したがって,この段階でpn−1個分のpを数えたことになる。

ただし,これだけでは足りない。例えばp2の倍数は p2⋅m の形をしているので,すでにpの倍数として1個分は数えられているが,さらにもう1個分のpを余分にもっている。したがって,p2の倍数の個数を追加で数える必要がある。その個数は pnp2=pn−2 個である。

同様に,p3の倍数は,pの倍数として1回,p2の倍数としてもう1回数えられたあと,さらに追加でもう1個分のpをもつ。その追加分は pnp3=pn−3 個である。

このように考えると,prの倍数は,pを少なくともr個含む数に対応しており,r個目のpを数えるために pnpr=pn−r 個を加えればよい。ただしr=1,2,…,nである。r=nのときはpnの倍数がちょうど1個あり,それより高いpn+1の倍数はpn以下には存在しない。

したがって,(pn)!に含まれる素因数pの個数は pn−1+pn−2+⋯+p+1 である。これは初項1,公比p,項数nの等比数列の和と見れば 1+p+p2+⋯+pn−1=pn−1p−1 である。よって求める回数は pn−1p−1 である。

別解

解法2

方針

en を (pn)! に含まれる素因数 p の個数とする。積のうち p の倍数だけを取り出すと、各倍数からまず p が1個ずつ現れ、残った積は (pn−1)! になる。これにより en=pn−1+en−1 を作り、初期値 e1=1 から解く。

解答

en を (pn)! の素因数分解に現れる p の個数とする。
1,2,…,pn のうち p を因数にもつ項だけを集めるとp⋅2p⋅3p⋯pn−1p=p pn−1(pn−1)!となる。したがって、p の倍数それぞれから取り出した pn−1 個分と、
残った (pn−1)! に含まれる分を合わせてen=pn−1+en−1である。

e1=1 なので、この漸化式を順に用いるとen=pn−1+pn−2+⋯+p+1=pn−1p−1.よって、(pn)! は p でpn−1p−1 回割り切れる。

総評

難度4、計算量3。目安時間は10分程度で,階乗に含まれる素因数の個数を数える標準問題である。単にpの倍数の個数だけを数えると,p2,p3,…の倍数がもつ追加のpを落としてしまう。p2の倍数は追加でもう1回,p3の倍数はさらにもう1回という「重複込み」の数え方を言葉で説明することが答案の中心である。最後はpn−1+pn−2+⋯+1を等比数列の和に直せばよい。計算は軽いが,なぜ倍数を何度も数えてよいのかを明確に書けるかで答案の説得力が大きく変わる。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る京大の整数の問題で問題集を作る

出典: 京都大学 2009年度 前期 数学(文系・理系甲共通)(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。