n!が10の40乗で割り切れるときの最小のn

【問題】
　n!が10^40(10の40乗)で割り切れるときの最小のnを求めよ。

【解答】
　10=2×5 であるからn!が10で40回割り切れるためには、
　n!が5で40回割り切れなければならない。
　また、そのときn!は2で40回割り切れる。
　　　　n=5　　のとき　5の倍数は 5÷5=1 (個)
　　　　n=5^2 　のとき　5の倍数は 25÷5=5 (個)
　　　　　　　　　　　　　　　　25÷25=1 (個)
　　　　n=5^3 のとき　5の倍数は 125÷5=25 (個)
　　　　　　　　　　　　　　　125÷25=5 (個)
　　　　　　　　　　　　　　　125÷125=1 (個)
　(25+5+1)+(5+1)+1+1+1=40 であるから、求める最小のnは
　　　　5^3+5^2+5+5+5=165


解答の意味がよくわかりません。
5で40回、2で40回割り切れるのはわかるが
なぜ、n=5,5^2,5^3の場合だけやる？
n=2,2^2,2^3,・・・は考慮しなくてよい？
それに最後の結論の２行がまったく意味不明です。。

ご教授宜しくお願いします。

No.5 回答者： info22_ 回答日時： 2011/09/06 14:26

>なぜ、n=5,5^2,5^3の場合だけやる？

>n=2,2^2,2^3,・・・は考慮しなくてよい？
n!を素因数分解するとn≧5で,因数2の個数の方が因数5の個数に比べてはるかに多くなります。なのでn!（n≧5）に含まれる因数5の個数だけ考慮すれば、含まれる2の個数の方は遥かに多いので,5の方だけ考慮すれば十分なのです。
2は2つ置きの偶数に含まれ、5は5つごとの末尾の桁が5か0の数にしか含まれないため
n!=n(n-1)(n-2)…3*2*1
の因数の中に出現する2の個数の方が5の個数に比べ遥かに多いのです。

以下を含まれる2,5,10の個数だけに注目してみてください。
10^kを括り出すと2が過剰に残っているかと思います。
n=5の時
5!=2^3*3*5
(=10*2^2*3)

n=5^2=25の時
(5^2)!=2^22*3^10*5^6*7^3*11^2*13*17*19*23
(=10^6*2^16*3^10*7^3*11^2*13*17*19*23)

n=5^3=125の時
(5^3)!=2^119*3^59*5^31*7^19*11^12*13^9*17^7*19^6*23^5*29^4*31^4*37^3*41^3*43^2
*47^2*53^2*59^2*61^2*67*71*73*79*83*89*97*101*103*107*109*113
(=10^31*2^88*3^59*7^19*11^12*13^9*17^7*19^6*23^5*29^4*31^4*37^3*41^3*43^2*47^2
*53^2*59^2*61^2*67*71*73*79*83*89*97*101*103*107*109*113
ここまでで含まれる因数10^mは、10^1,10^6,10^31と急に増えていますね。
あと因数5を「40-31=9」個含むようにnを増加してやります。
n=125+5=130で因数5の個数が1増加します。
n=125+10=135で因数5の個数が1増加します。
…
因数5の個数を9個増やすには
n=125+5*9=125+45=170
とすれば良い様に見えますが、増やしたnの中に25の倍数が1個含まれる(n=150)ので
とその分nの値を調整(5だけ減らす）してやらないといけませんね。
つまりn=170-5=165

>それに最後の結論の２行がまったく意味不明です。
>(25+5+1)+(5+1)+1+1+1=40 であるから、求める最小のnは
>　　　　5^3+5^2+5+5+5=165
(25+5+1)について
(5^3)!=125!に含まれる因数5の個数です。
　25は　125!に含まれる5の倍数の個数で125÷5=25から出した個数です。
　　　　つまり、5,10,15,20,25,30, … ,120,125 の個数です。
　　　　この中には 25=5^2の倍数,　125=5^3も含まれます。
　　　　この分125!の中には25個より多い5が含まれます。
　+5は　125!に含まれる25の倍数の個数です。125÷25=5から出した個数です。
　　　　つまり、25,50,75,100,125の5個で、これらは因数に5^2を持ちますので
　　　　2個分として数えます。5の倍数で1個分カウント済みなので、ここでは
　　　　25の倍数の個数分だけカウントします。この中には125=5^3が含まれています。
　　　　因数5の個数を3とカウントしないといけません。ここまでで2個分カウント
　　　（5の倍数、25の倍数としてカウント）済みになります。
　+1は　125!に含まれる125=5^3の倍数の個数で1個です。125には因数の5が3個含まれます
　　　　が,すでに5の倍数、25の倍数の個数で2個分カウント済みなので残り1個をカウント
　　　　します。
　まとめると、(5^3)!=125! に含まれる因数5の個数は(25+5+1)=31個となります。

(5+1)について
残りの40-31=9個ですが。
　まず150!/125!=126*127* … *130までに含まれる5の個数を調べると
　5の倍数は
　150÷5 -125÷5=30-25=5個です。
この5個の中に25=5^2の倍数は
　 150=5^2*2*3
　が含まれます。これば2個としてカウントすべきですが5の倍数でもあるので
　すでに1個分カウント済みなので1個分加えて
126～150までの積に含まれる5の個数は合計で(5+1)=6となるわけです。

「+1+1+1」について
残りの　40-(31+6)=3個分の5を加えるには
　因数として、因数として5を含む
　 155,160,165(いずれも25=5^2を持たない)の3つの数を掛けて「165!」とすることで
「+1+1+1」と加えねばならない。
つまり、5^40を約数にもつ最小のn!は165!ということになる。

以上が「(25+5+1)+(5+1)+1+1+1=40」…(▲)の意味です。

これから最小のnは
>5^3+5^2+5+5+5=165
となります。

5^3=125の意味
n=125まででn!は31個の5を因数に持つということ（因数5の数31項）　

+5^2の意味
n=125に5^2=25加えればn=150でn!/125!の分で6個の因数5を増やせる（合計37個）。

+1+1+1の意味
n=150に5を3回加えたn=150+5*3=165でn!/150!の分で3個の因数5を増やせる(合計40個)

ということです。

No.4 回答者： girlkeeper 回答日時： 2011/09/06 06:45

少しだけ設問を変えます。

問：ｍが１２５！のとき、ｍの末尾に０は幾つ並ぶか？

「０の並ぶ個数」ってことは１０の何乗で割れるかってことです。

解き方もよく似ていて、因数５が何個でてくるかを数えます。

で、第１のご質問。「なぜ因数２の個数は数えなくてもいいか」

末尾に並ぶ０の個数は、２，５のうち、個数の「少ない方」に支配されます。

ｍ＝１０で考えると、因数５は　５，１０の2個、因数２は単純に考えて２，４，６，８，１０の5個。しかも４からもう1個、さらに８から2個（２×２×２）出てくるので、8個も出てきます。

２×５を作ろうとすると、５の方が全然たりないのが分かります。ｍが大きくなってもこれは同じ。
だから２^2や２^3などは考えなくていい。


第2のご質問。

仮にｎ＝１２５とすると、５の倍数が１２５÷５＝２５、２５の倍数が１２５÷２５＝５、１２５の倍数が１２５÷１２５＝１　　で、２５＋５＋１＝３１（個）

求めたいのは40個になるときだから、これでは9個足りない。
そこでｎを２５増やして１２５＋２５＝１５０にしてみる。
１から数え直してもいいけど、せっかく31個数えたので、増やした分だけで考える。

５の倍数が２５÷５＝５、２５の倍数が２５÷２５＝１、１２５の倍数はない。
そこで　５＋１＝６　　で、さっきの31個とたして37個でまだ足りない。

3個増やすために５×３だけ大きい　１５０＋５×３＝１６５

５の倍数が4個に満たなければいいので１６９でも40個になるだけど「最小のｎ」なので１６５　

No.3 回答者： s1013129 回答日時： 2011/09/06 06:29

【改訂版】

打ち間違いがあったので再び失礼


n! の素因数に5が40個含まれるときが、求めるnです。

素因数として５が40個含まれるとき、2は必ず40個以上含まれますよね。
たとえば、
5! =1*2*3*4*5 = 1*2*3*(2*2)*5 ・・・5が１個、２が3個
10! = 1*2*3*4*5*6*7*8*9*10 = 1*2*3*(2*2)*5*(2*3)*7*(2*2*2)*(3*3)*(2*5) ・・・５が２個、２が8個
n!がもっと大きくなっても素因数の個数は５より２のほうが沢山出てきます。
だから、2の素因数の個数を考慮しなくて良いのです。


n! = 25! のとき、素因数として5が何個含まれるかというと、
25! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25
25! = 1*2*3*4*5*6*7*8*9*(5*2)*11*12*13*14*(5*3)*16*17*18*19*(5*4)*21*22*23*24*(5*5)
だから、6個
２５！は、１～２５を掛けていくから、
１～２５のうちの5の倍数の個数、たす、25の倍数の個数をしてやれば、素因数として５を何個含むかが出てきます。


n! = 125! のときは、１～１２５のうちの、
５の倍数の数＋25の倍数の個数＋１２５の倍数の個数＝素因数として５を含む個数
となるから、
１２５÷５＋１２５÷２５＋１２５÷１２５＝３１個

40個に近づいてきました

ところが、n! = 625!のとき、１～６２５のうちの、
５の倍数の数＋25の倍数の個数＋１２５の倍数の個数＋６２５の倍数の個数＝素因数として５を含む個数
だから、
６２５÷５＋６２５÷２５＋６２５÷１２５＋６２５÷６２５＝１５６個
となり、40個をオーバーしてしまいます。
求めるnは最小のものだから、５が４０含まれていればよいのです。


ここで、さっきのn! = 125! では５が31個だったので、ここから少しずつnを大きくすれば５が４０個となるときが
すぐに見つかりそうですね。

nを少し大きくしてn! = 130! ではどうなるでしょう。
130！ = 130*129*128*127*126*125！ = (5*26)*129*128*127*126*125！
だから、32個になります。
135！なら33個
140！なら34個
145！なら35個
150！では？37個ですね。150は5*5*3だからです。
155！なら38個
160！なら39個
165！でついに40個です。

ここが【解答】の　(25+5+1)+(5+1)+1+1+1=40　という式がでてくる部分にあたります

(25+5+1)は125！が含む5の個数
（5＋1）は 126*127*・・・*150が含む５の個数
つまり150！は（25+5+1）+(5+1) = 37個の5を含みます。
あと3つ必要ですから
155！、160！、165！と微調整して40個ぴったりです
＋１＋１＋１はnを５ずつ増やして5の個数を1個ずつ増やして40個に近づけていっているということですね。

よって
n = 5^3 = 125　のとき　(25+5+1) = 31個
n = 5^3+5^2 = 150　のとき　(25+5+1)+(5+1) = 37個
n = 5^3+5^2+5+5+5 = 165　のとき　(25+5+1)+(5+1)+1+1+1 = 40個

No.2 回答者： s1013129 回答日時： 2011/09/06 06:25

n! の素因数に5が40個含まれるときが、求めるnです。

素因数として５が40個含まれるとき、2は必ず40個含まれますよね。
たとえば、
5! =1*2*3*4*5 = 1*2*3*2*2*5 ・・・5が１個、２が3個
10! = 1*2*3*4*5*6*7*8*9*10 = 1*2*3*2*2*5*2*3*7*2*2*2*3*3*2*5 ・・・５が２個、２が8個
n!がもっと大きくなっても素因数の個数は５より２のほうが沢山出てきます。
だから、2の素因数の個数を考慮しなくて良いのです。


n! = 25! のとき、素因数として5が何個含まれるかというと、
25! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25
25! = 1*2*3*4*5*6*7*8*9*(5*2)*11*12*13*14*(5*3)*16*17*18*19*(5*4)*21*22*23*24*(5*5)
だから、6個
２５！は、１～２５を掛けていくから、
１～２５のうちの5の倍数の個数、たす、25の倍数の個数をしてやれば、素因数として５を何個含むかが出てきます。


n! = 125! のときは、１～１２５のうちの、
５の倍数の数＋25の倍数の個数＋１２５の倍数の個数＝素因数として５を含む個数
となるから、
１２５÷５＋１２５÷２５＋１２５÷１２５＝３１個

40個に近づいてきました

ところが、n! = 625!のとき、１～６２５のうちの、
５の倍数の数＋25の倍数の個数＋１２５の倍数の個数＋６２５の倍数の個数＝素因数として５を含む個数
だから、
６２５÷５＋６２５÷２５＋６２５÷１２５＋６２５÷６２５＝１５６個
となり、40個をオーバーしてしまいます。
求めるnは最小のものだから、５が４０含まれていればよいのです。


ここで、さっきのn! = 125! では５が31個だったので、ここから少しずつnを大きくすれば５が４０個となるときが
すぐに見つかりそうですね。

nを少し大きくしてn! = 130! ではどうなるでしょう。
130！ = 130*129*128*127*126*125！ = (5*26)*129*128*127*126*125！
だから、32個になります。
135！なら33個
140！なら34個
145！なら35個
150！では？37個ですね。150は5*5*3だからです。
155！なら38個
160！なら39個
165！でついに40個です。

ここが【解答】の　(25+5+1)+(5+1)+1+1+1=40　という式がでてくる部分にあたります

(25+5+1)は125！が含む5の個数
（5＋1）は 126*127*・・・*150が含む５の個数
つまり150！は（25+5+1）+(5+1) = 37個の5を含みます。
あと3つ必要ですから
155！、160！、165！と微調整して40個ぴったりです
＋１＋１＋１はnを５ずつ増やして5の個数を1個ずつ増やして40個に近づけていっているということですね。

よって
n = 5^3 = 125　のとき　(25+5+1) = 31個
n = 5^3+5^2 = 150　のとき　(25+5+1)+(5+1) = 37個
n = 5^3+5^2+5+5+5 = 165　のとき　(25+5+1)+(5+1)+1+1+1 = 40個

No.1 回答者： nananotanu 回答日時： 2011/09/06 06:11

「また、そのときn!は2で40回割り切れる」はどうしてでしょう？

>最後の結論の２行がまったく意味不明
手計算でやっていったら、n=5^3 までで40個に達したから終わり、ってだけでは？
(条件を満たしたから)
NGだったらn=5^4も計算しただけのこと