数学A 整数問題 問題 105 解説

方針・初手

$50!$ が $3^n$ で割り切れる最大の $n$ は、$50!$ の素因数分解に含まれる素因数 $3$ の個数である。

したがって、$1$ から $50$ までの整数の中に含まれる $3$ の因数の個数を数える。

解法1

$50!$ は

$$ 50!=1\cdot 2\cdot 3\cdots 50 $$

である。

この積の中で、$3$ の倍数は少なくとも $3$ を $1$ 個含む。個数は

$$ \left\lfloor \frac{50}{3} \right\rfloor=16 $$

である。

ただし、$9=3^2$ の倍数は $3$ をさらにもう $1$ 個含むので、その分を追加で数える。個数は

$$ \left\lfloor \frac{50}{9} \right\rfloor=5 $$

である。

さらに、$27=3^3$ の倍数は $3$ をさらにもう $1$ 個含むので、その分も追加で数える。個数は

$$ \left\lfloor \frac{50}{27} \right\rfloor=1 $$

である。

$81=3^4$ は $50$ より大きいので、これ以上は数える必要がない。

よって、$50!$ に含まれる素因数 $3$ の個数は

$$ 16+5+1=22 $$

である。

したがって、$50!$ は $3^{22}$ で割り切れるが、$3^{23}$ では割り切れない。

解説

階乗 $m!$ に含まれる素因数 $p$ の個数は

$$ \left\lfloor \frac{m}{p} \right\rfloor+ \left\lfloor \frac{m}{p^2} \right\rfloor+ \left\lfloor \frac{m}{p^3} \right\rfloor+\cdots $$

で求める。

この問題では、$3$ の倍数、$9$ の倍数、$27$ の倍数を順に数えることが重要である。特に、$9,18,27,\dots$ のような数は $3$ を複数個含むため、$3$ の倍数だけを数えると不足する。

答え

$$ 22 $$