n!はmで何回割り切れるか問題

上野竜生です。○!は△で何回割り切れるか?というタイプの問題を解説します。

n!はmで何回割り切れるか問題

スポンサーリンク

パターン1 基本(mが素数の場合)

100!は2で何回割り切れるか?
答え1から100までの中に
2で割り切れるものは50個ある。(この時点で50回は割り切れる)
さらに4で割り切れるもの1つにつき1回ずつ割り切れる(4で割り切れれば2で2回割り切れるが1回分はすでにカウント済みなのであと1回ずつ足す)
4で割り切れるものは25個(この時点で75回は割り切れる)
さらに8で割り切れるもの1つにつき1回ずつ割り切れる(8で割り切れれば2で3回割り切れるが2回分はすでにカウント済みなのであと1回ずつ足す)
8で割り切れるものは12個(この時点で87回は割り切れる)
同様に16で割り切れるもの6個
32で割り切れるもの3個
64で割り切れるもの1個を足すと97回は割り切れる。
128で割り切れるものはないのでこれで終わりであり,100!は2で97回割り切れる。
このタイプの問題は割と有名なのでここまで丁寧に書く必要はないですがまず理解してもらうために丁寧に書きました。次の問題はほぼ同様の問題ですが解答量としては次の模範解答ぐらいで十分です。
100!は5でm回割り切れるがm+1回は割り切れないという。整数mの値を求めよ。

答え1から100までに5の倍数が20個,52の倍数が4個あるのでm=20+4=24

計算そのものについて,100÷5=20,100÷25=4という計算をせず
100÷5=20,20÷5=4という計算をする方が楽です。
例題1なら
100÷2=50 , 50÷2=25, 25÷2=12あまり1 , 12÷2=6 , 6÷2=3 , 3÷2=1あまり1 という風に計算するほうが早いです。
25÷2=12.5ですがこの「.5」は切り捨てて問題ありません。

パターン2 mが素数じゃない場合

100!を計算すると末尾に0がいくつ続くか

つまり10で何回割り切れるかということなのでパターン1とほぼ同じです。

しかし10=2×5なので2で割り切れる回数と5で割り切れる回数を調べてより少ないほうに合わせられます。明らかに5で割り切れる回数のほうが少ないので結局パターン1例題2と全く同じ問題です。

答え5で何回割り切れるかを調べればよい。
パターン1の2つめの例題より24個。

今回は明らかに2よりも5のほうが少ないですが微妙なときは実際両方計算する必要があります。

(1) 255!は12で何回割り切れるか?
(2) 256!は12で何回割り切れるか?

12=22×3なので2と3で何回割り切れるかを調べる必要がありますね。

答え(1) 1から255の中に
2の倍数は127個,22の倍数63個,23の倍数31個,24の倍数15個,25の倍数7個,26の倍数3個,27の倍数1個があるので255!が2で割り切れる回数は
127+63+31+15+7+3+1=247回
一方1から255の中に
3の倍数85個,32の倍数28個,33の倍数9個,34の倍数3個,35の倍数1個あるので255!が3で割り切れる回数は
85+28+9+3+1=126回
12で割り切れるためには2で2回,3で1回ずつ割り切れる必要があるので
247÷2=123.5<126より123回割り切れる。
(2) 256は2で8回割り切れるが3では割り切れないので
256!は2で247+8=255回,3で126回割り切れる。
255÷2=127.5>126より12で126回割り切れる。

(1)では2のほうが少なく,(2)では3のほうが少ないです。こういう微妙な場合もあるのでこの場合は両方調べましょう。

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする