今回は階乗を計算したときに末尾に連続して並ぶ0の個数を求めたり、同じ素因数で割り切れる回数の求め方について分かりやすく解説していこうと思います。多くの問題では階乗の値が具体的には計算できないくらい大きな値になっているので、解答にあたっては求めるべき素因数を見極めて効率よく個数を数え上げるという工夫が必要になります。
そこで本記事では、問題パターンごとの解き方・考え方のコツと素因数を求める裏ワザ（ルジャンドルの定理）について解説したのち、応用問題を解くカギとなる着眼点について分かりやすく解説していこうと思います。
『素因数の個数の求め方』を用いて解けばOK！
≪問題パターン≫
・同じ素数\(\small p\)で割り切れる回数を求める問題【基本問題1】【応用問題2】
⇒素因数\(\small p\)がいくつ含まれるかの問題に帰着
・\(\small p\)進数で表したときの末尾の0の個数を求める問題【応用問題3】
⇒素因数\(\small p\)がいくつ含まれるかの問題に帰着
・末尾の0の個数を求める問題【基本問題2】【応用問題1】
⇒素因数5がいくつ含まれるかを求める問題に帰着
- 末尾に並ぶ0の個数の求め方について知りたい人
- 階乗に含まれる素因数の個数（割り切れる回数）の求め方について知りたい人
- 応用問題の解き方を理解したい人
- 大学入試対策、定期テスト対策がしたい人
【基礎講義】階乗と素因数の個数
【講義1】素因数の個数＝割り切れる回数
階乗に含まれる素因数の個数を求める問題をよく見かけると思いますが、そもそも素因数の個数を求めるとはどういうことか改めて確認しておきましょう。
先に結論を言ってしまうと、素因数の個数とは特定の素因数で割り切れる回数と理解しておけばOKです。どうしてそうなるのかこれから説明していきます。
まず、素因数という言葉が分かりずらいですが、ある整数を因数分解したときに素数であれば素因数と言います。たとえば、6を\(\small 6 = 2 \times 3\)と因数分解した場合、2や3は素数なので素因数と言います。逆に、\(\small 6 = 1 \times 6\)みたいに因数分解した場合は、1や6は素数ではないので、素因数とは言わずただ単に因数と言います。
よって、素因数の個数を求めるとは、ある数を素因数分解したときに特定の素因数が含まれている何個を求めることだと言い換えることができます。そして、素因数の個数の分だけ割り算できることから、割り切れる回数と考えることができます。
では、具体例を通して確認していきましょう。
\(\small 12\) には素因数2が何個含まれるか。
（解説＆解答）
いきなり階乗に含まれる素因数について考えると難しいので、まずは整数に含まれる素因数の個数を求めることを考えてみましょう。12は素因数分解すると\(\small 12 = \color{red}{2^2} \times 3\)なので、素因数2は2個含まれることが分かります。よって答えは2個です。
一方で、\(\small 12 = 2^2 \times 3\)であることから、「2」が2個（2乗なので）含まれるので、12は2で2回割り切ることができます。このことからもわかる通り、素因数2の個数と2で割り切れる回数は同じことを意味していることが分かるでしょう。
では、本題の階乗に含まれる素因数の個数の求め方について考え方を解説していきます。
\(\small 12!\) には素因数2が何個含まれるか。
（解説＆解答）
例題1のように\(\small 12!\)を素因数分解しようとしても、\(\small 12! = 12 \times 11 \times \cdots 3 \times 2 \times 1\)というとてつもなく計算が大変な数なので、具体的な値を求めるのは厳しそうです…。
ここで、着眼したいのが、知りたいのは\(\small 12!\)の計算結果ではなく、あくまで\(\small 12!\)に含まれる「2」の個数という点です。2の個数だけであれば、\(\small 12!\)の値を求めなくても計算はできそうです。
たとえば、\(\small 12! = 12 \times 11 \times \cdots 3 \times 2 \times 1\)なので、積の1番目の12に着目すれば\(\small 12 = 2^2 \times 3\)なので素因数2の個数は2個、積の2番目の11であれば2の倍数ではないので素因数2の個数は0個になります。これを頑張って残りの数についても整理すると下図のようになります。
\(\small 12!\)は1～12までの数の積なので、それぞれの数を横に並べて、その下に素因数2の個数を記載しています。また、個数ごとに分かりやすくなるように色付けしています。
この結果を見てまず気が付くのが、奇数は2を持たないので素因数2の個数は0個になります（灰色箇所）。もう一つ分かることとしては、\(\small 8=2^3\)の倍数は素因数2の個数が3個、\(\small 4=2^2\)の倍数は素因数2の個数が2個、\(\small 2=2^1\)の倍数は素因数2の個数が1個であることが分かります。
なので、\(\small 12!\)に含まれる素因数2の個数は上表の素因数2の個数の合計である\(\small 10\)個が答えになります。
でも、この求め方だと\(\small n!\)の\(\small n\)の値が大きな数の場合、一つ一つ素因数の個数を計算しなければならず大変です…。もっと効率的な求め方はないでしょうか？
【講義2】【裏ワザ】階乗に含まれる素因数の個数の求め方（ルジャンドルの定理）
本章では、例題2の問題についてより効率的な素因数の個数の求め方を解説していきます！
先程までは1～12までの各数ごとに素因数2がいくつ含まれるかをチェックしていきましたが、結局求めたいのは1～12までに含まれる素因数2の合計数なので、各数ごとの素因数2の個数ではなく、12以下の整数に含まれる素因数2の個数を数え上げる方が効率的です。
そこで各数ごとに素因数2の個数を「〇」の個数で表現し直してみましょう（下図）。たとえば、12であれば素因数2の個数は2個なので「〇」を2個記載するイメージです。
このように考えると、\(\small 12!\)に含まれる素因数2の個数は、表中の「〇」の個数を数え上げればよいことになります。
すると、一番上の段の「〇」の個数は1～12までの2の倍数の個数に相当するため、12÷2=6個と求めることができます。次に中段の「〇」の個数は1～12までの4の倍数の個数に相当するため、12÷4=3個と求めることができます。最後に下段の「〇」の個数は1～12までの8の倍数の個数に相当するため、12÷8＝1あまり4なので、1個と求めることができます。
【考察】\(\small 2^n\)の倍数の個数を求めることで素因数2の個数が求まる理由
なぜこのような計算によって素因数の個数が求まるのかと言うと、たとえば8であれば、素因数2が3個あるワケですが、これは2の倍数でもあり、4の倍数でもあり、8の倍数でもあるため合計3個になるワケです。12であれば2の倍数かつ4の倍数なので2個になります。
これは見方を変えれば、1～12までの整数の中に含まれる2の倍数の個数と4の倍数の個数と8の倍数の個数を求めていることと同じなので、それぞれの倍数の個数を求めて合計することで素因数2の個数を求めることができるわけです。
あとは、それぞれの段で求めた個数を合計することで、\(\small 6+3+1=10\)個と求めることができます。
以上の結果をまとめると、一般的に階乗に含まれる素因数2の個数は次のように求めることができます。
≪\(\small n!\)に含まれる素因数2の個数≫
（\(\small n!\)に含まれる素因数2の個数）\(\small =\)『\(\small n\)÷\(\small 2\)の整数部分』+『\(\small n\)÷\(\small 2^2\)の整数部分』+ …
この公式を用いて例題2を解くと
\begin{split}
&\small（12!に含まれる素因数2の個数）\\
&\small =『12÷2の整数部分』+『12÷4の整数部分』\\
&\small +『12÷8の整数部分』+『12÷16の整数部分』\\
&\small + \cdots\\
&\small =6+3+1+0+ \cdots\\
&\small =10\\
\end{split}
のように求めることができます。ちなみに、12÷16以降は、割る数 > 割られる数（今回なら12）となるのですべて0になります。
さらに、ここまでは素因数が2の場合でずっと説明してきましたが、この考え方は素因数が3でも5でもどんな値でも同じ話になるので、一般的に\(\small n!\)に含まれる素因数 \(\small p\)の個数は以下のように求めることができます。
\begin{split} &\small（素因数の個数）\\ &\small =\left(pの倍数の個数\right)+\left(p^2の倍数の個数\right)\\ &\small \quad +\left(p^3の倍数の個数\right)+ \cdots\\ &\small =\color{#ef5350}{\left(\frac{n}{p}の整数部分\right)+\left(\frac{n}{p^2}の整数部分\right)}\\ &\small \quad \color{#ef5350}{+\left(\frac{n}{p^3}の整数部分\right)+ \cdots}\\ \end{split}
≪補足1≫
『\(\small \displaystyle \frac{n}{p}\)の整数部分』という部分が日本語が含まれていて少しカッコ悪いと感じる人向けに、ガウス記号を用いることで上記の公式を
$$\small \displaystyle \left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\cdots$$
※ただし、ガウス記号\(\small [x]\)は\(\small x\)を超えない最大の整数を表す
のようにカッコよく表現することができるので参考までに紹介しておきます。
さらに、この式は数Ⅱで習う和の記号（シグマ）を用いれば
$$\small \displaystyle \sum_{k=1}^\infty \left[\frac{n}{p^k}\right]$$
※ただし\(\small \infty\)は和が無限に続くことを表す
と非常にすっきりとした形で表現できます。ちなみにこの公式はルジャンドルの定理と呼ばれています。
≪補足2≫
ルジャンドルの定理を紹介するとよく
$$\small \displaystyle \left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\cdots$$
の公式の分子が\(\small n!\)じゃなくて\(\small n\)なのはなんで？という質問をもらいます。
これは、\(\small n! = n(n-1)\times \cdots \times 2 \times 1\)のように\(\small 1～n\)の積なので、\(\small 1～n\)の中に含まれる素因数 \(\small p\)の個数を求めるには\(\small n\)以下の\(\small p^n\)の倍数を求める必要があるので、分子\(\small n\)を\(\small p\)や\(\small p^2\)などで割り算して倍数の個数を求めているからです。
【問題＆解説】階乗に含まれる素因数の個数
階乗に含まれる素因数の個数の求め方が分かったところで、実際の問題を通して理解を深めていきましょう。
（1）\(\small 50!\) に含まれる素因数\(\small 5\)の個数を求めよ。
（2）\(\small 100!\) は\(\small 7\)で何回割り切れるか。
（3）\(\small 80!\) の末尾には\(\small 0\)が連続して何個並ぶか。
↓↓各問題の解説はこちら
（1）\(\small \displaystyle \frac{200!}{40!}\) の末尾には\(\small 0\)が連続して何個並ぶか。
（2）\(\small (3^{6})!\) は\(\small 3\)で何回割り切れるか。
（3）\(\small 20!\) を\(\small 3\)進法で表したとき、末尾に連続して並ぶ\(\small 0\)の個数を求めよ。
↓↓各問題の解説はこちら
【基本問題1】階乗に含まれる素因数の個数
（1）\(\small 50!\) に含まれる素因数\(\small 5\)の個数を求めよ。
（2）\(\small 100!\) は\(\small 7\)で何回割り切れるか。
\begin{split}
&\small（素因数の個数）\\ &\small =\left(\frac{n}{p}の整数部分\right)+\left(\frac{n}{p^2}の整数部分\right)\\
&\small \quad +\left(\frac{n}{p^3}の整数部分\right)+ \cdots\
\end{split}
で求められる。
・階乗を素数\(\small p\)で何回割り切れるかを求めるという問題は、階乗に含まれる素因数\(\small p\)が何個かを求める問題と同義。
\(\small 50!\)に含まれる素因数\(\small 5\)の個数は、\(\small 50! = 50 \times 49 \times \cdots \times 2 \times 1\)であることから、\(\small 1～50\)までの整数に含まれる素因数\(\small 5\)の個数を求めることと同じである。
よって、\(\small 1～50\)までの整数の中に\(\small 5^n\)の倍数がそれぞれいくつ含まれるかを順番に確認していけばよい。
\(\small 5^n\)の倍数の個数
・\(\small 5\)の倍数の個数 ⇒\(\small 50÷5=10\)個
・\(\small 5^2=25\)の倍数の個数 ⇒\(\small 50÷25=2\)個
・\(\small 5^3=125\)の倍数の個数 ⇒\(\small 50÷125=0.4\)。故に\(\small 0\)個
・\(\small 5^4\)の倍数以降も\(\small 50\)を越えるため\(\small 0\)個
よって、素因数5の個数は10+2=12個…【答】
【別解】ルジャンドルの定理を利用した解法
【講義2】で紹介した公式を利用して
\begin{split}
&\small \left[\frac{50}{5}\right]+\left[\frac{50}{5^2}\right]+\left[\frac{50}{5^3}\right]+\cdots\\
&\small =\left[10\right]+\left[2\right]+\left[\frac{2}{5}\right]+\cdots\\
&\small =10+2+0+\cdots ◀3項目以降はすべて0\\
&\small =12\\
\end{split}
のように計算してもよいが、単純な公式暗記ではなく考え方をしっかり理解しておくことをおすすめする。\(\small 50!\)に含まれる素因数5の個数は\(\small 1～50\)までの\(\small 5^n\)の倍数の個数の合計値という考え方を理解していれば自ずとルジャンドルの定理の計算式を導くことが可能である。
\(\small 100!\)が7で何回割り切れるかを求める問題は、\(\small 100!\)に素因数7が何個含まれるかを求める問題と読み替えることができる [*1]。
*1：【補足】
たとえば、\(\small 48\)は\(\small \color{#ef5350}{2^4} \times 3\)と素因数分解できるので、『素因数2が4個含まれる』＝『2で4回割り算できる』ということ。
よって、（1）と同様に\(\small 1～100\)までの整数の中に\(\small 7^n\)の倍数がそれぞれいくつ含まれるかを順番に確認していく。
\(\small 7^n\)の倍数の個数
・\(\small 7\)の倍数の個数 ⇒\(\small 100÷7 ⇒ 14\)個
・\(\small 7^2=49\)の倍数の個数 ⇒\(\small 100÷49 ⇒ 2\)個
・\(\small 7^3=343\)の倍数の個数 ⇒\(\small 100\)を越えるため\(\small 0\)個
・\(\small 7^4\)の倍数以降も\(\small 100\)を越えるため\(\small 0\)個
よって、\(\small 100!\)に含まれる素因数7の個数は\(\small 14+2=16\)なので、\(\small 100!\)は\(\small 7\)で16回割り切れる…【答】.
【基本問題2】階乗の末尾に並ぶ0の個数
（3）\(\small 80!\) の末尾には\(\small 0\)が連続して何個並ぶか。
☞\(\small 80!\)に含まれる素因数\(\small 5\)の個数を求める問題に帰着できる！
末尾に連続して並ぶ\(\small 0\)の個数を求めるには、因数に\(\small 10\)がいくつ含まれるかが分かればよい [*1]。
*1：【補足】末尾の\(\small 0\)の個数
どんな数でも\(\small 10\)倍すると末尾に\(\small 0\)が一つ増えるので、『末尾の\(\small 0\)の個数』＝『因数\(\small 10\)の個数』となる。
たとえば、\(\small 102000\)のような数の場合、末尾に並ぶ\(\small 0\)の個数は3個になるが、これは\(\small 102000 = 102 \times 10^3\)のように因数に\(\small 10\)が3つ含まれるからとも説明できる。
\(\small 80!\)に含まれる因数\(\small 10\)の個数を求めるには、\(\small 10 = 2 \times 5\)と素因数分解できるので、素因数 \(\small 2,5\)のペアが何組できるかを求めればよいだろう。
愚直に素因数 \(\small 2\)の個数と素因数\(\small 5\)の個数をそれぞれ求めてから、何組のペアが作れるかを計算してもよいが、結局ペアを作るときには素因数 \(\small 2,5\)のうち、個数が少ない素因数の個数分しかペアが作れない [*2]ので、少ない方の素因数の個数だけ求めればよい 。
*2：【補足】素因数のペアの個数は少ない素因数の個数に着目すればよい理由
ルジャンドルの定理より、\(\small 80!\)に含まれる素因数\(\small 2\)の個数は
\begin{split}
&\small \left[ \frac{80}{2}\right]+\left[ \frac{80}{2^2}\right]+\cdots+\left[ \frac{80}{2^5}\right]+\left[ \frac{80}{2^6}\right]+\cdots\\
&\small = 40+20+10+5+2+1+0+\cdots\\
&\small = 78\\
\end{split}
素因数 \(\small 5\)の個数は
\begin{split}
&\small \left[ \frac{80}{5}\right]+\left[ \frac{80}{5^2}\right]+\left[ \frac{80}{5^3}\right]+\cdots\\
&\small = 16+3+0+\cdots\\
&\small = 19\\
\end{split}
よって、\(\small 2 \times 5\)のペア自体は\(\small 19\)組作れることになる。
素因数\(\small 2\)と\(\small 5\)の個数を比較すると、素因数\(\small 5\)の個数の方が少ない（\(\small 2\)の倍数と\(\small 5\)の倍数だと\(\small 5\)の倍数の方が少ない）ので、今回は\(\small 80!\)に含まれる素因数\(\small 5\)の個数を求めればOK。
よって、1～80の中に含まれる\(\small 5^n\)の倍数の個数を求めていけばよいので
\(\small 5^n\)の倍数の個数
・\(\small 5\)の倍数の個数 ⇒\(\small 80÷5 ⇒ 16\)個
・\(\small 5^2=25\)の倍数の個数 ⇒\(\small 80÷25 ⇒ 3\)個
・\(\small 5^3=125\)の倍数の個数 ⇒\(\small 80\)を越えるため\(\small 0\)個
・\(\small 5^4\)の倍数以降も\(\small 80\)を越えるため\(\small 0\)個
より、合計で\(\small 16+3=19\)個の素因数 \(\small 5\)が含まれることが分かる。
よって、因数\(\small 2 \times 5 =10\)が\(\small 19\)個作れるので、\(\small 10^{19}\)すなわち末尾に連続して並ぶ\(\small 0\)の個数は\(\small 19\)個…【答】.
【深堀検討】\(\small 80!\)に含まれる\(\small 10^n\)の倍数の個数を求めるではだめ？
\(\small 80!\)に含まれる因数\(\small 10\)の個数を求めるために、\(\small 10\)の倍数、\(\small 100\)の倍数、… 、の個数を求める方針ではだめなのかという疑問を持った人もいるかもしれないが、この方法だと一つの数字の中に\(\small 10\)の因数が含まれる場合はカウントされるが、\(\small 2\)の倍数に含まれる素因数\(\small 2\)と\(\small 5\)の倍数に含まれる素因数\(\small 5\)を組み合わせて因数\(\small 10\)ができるようなパターンが漏れてしまうため、解答にあるように素因数\(\small 2,5\)の個数それぞれで考えてあげる必要がある。
【応用問題1】末尾に並ぶ0の個数（分数型）
（1）\(\small \displaystyle \frac{200!}{40!}\) の末尾には\(\small 0\)が連続して何個並ぶか。
考え方自体は基本問題（3）と同様で、\(\small \displaystyle \frac{200!}{40!}\)に含まれる素因数\(\small 2,5\)のペアの個数が求められればよい。
本問は階乗の割り算になっているので、分子の階乗に含まれる素因数\(\small 2,5\)のペアの個数から、分母の階乗に含まれる素因数\(\small 2,5\)のペアの個数を引き算することで、全体に含まれる素因数\(\small 2,5\)のペアの個数を求める方針で解いていく。
[1] \(\small 200!\)の階乗に含まれる素因数\(\small 2,5\)のペアの個数
素因数\(\small 5\)の個数の方が少ないので、『ペアの個数＝素因数\(\small 5\)の個数』であることから、
・\(\small 5\)の倍数の個数 ⇒ \(\small 200÷5 ⇒ 40\)個
・\(\small 5^2=25\)の倍数の個数 ⇒ \(\small 200÷25 ⇒ 8\)個
・\(\small 5^3=125\)の倍数の個数 ⇒ \(\small 200÷125 ⇒ 1\)個
・\(\small 5^4=625\)の倍数以降は\(\small 200\)を越えるため\(\small 0\)個
よって、素因数\(\small 5\)の個数（＝素因数\(\small 2,5\)のペアの個数）は\(\small 40+8+1=\)\(\small 49\)個…①.
[2] \(\small 40!\)の階乗に含まれる素因数\(\small 2,5\)のペアの個数
同様に素因数\(\small 5\)の個数を求めると
・\(\small 5\)の倍数の個数 ⇒ \(\small 40÷5 ⇒ 8\)個
・\(\small 5^2=25\)の倍数の個数 ⇒ \(\small 40÷25 ⇒ 1\)個
・\(\small 5^3=125\)の倍数以降は\(\small 40\)を越えるため\(\small 0\)個
よって、素因数\(\small 5\)の個数（＝素因数\(\small 2,5\)のペアの個数）は\(\small 8+1=\)\(\small 9\)個…②.
よって、\(\small \displaystyle \frac{200!}{40!}\)に含まれる素因数\(\small 2,5\)のペアの個数は、① \(\small -\) ②で求めることができるので、
\(\small 49 – 9= \color{red}{40}\)個…【答】.
【応用問題2】\(\small (p^n)!\)に含まれる素因数の個数
（2）\(\small (3^{6})!\) は\(\small 3\)で何回割り切れるか。
・数Ⅱの数列を学習している人であれば数列の和の公式を用いることで簡単に求めることができる。
\(\small (3^{6})!\)に含まれる素因数3の個数を求めればよい。
\(\small 3^n\)の倍数の個数
・\(\small 3\)の倍数の個数 ⇒\(\small 3^{6}÷3 \space ⇒ 3^{5}\)個
・\(\small 3^2\)の倍数の個数 ⇒\(\small 3^{6}÷3^{2} ⇒ 3^{4}\)個
…
・\(\small 3^{6}\)の倍数の個数 ⇒\(\small 3^{6}÷3^{6} ⇒ 1\)個
・\(\small 3^{7}\)の倍数以降は\(\small 3^{6}\)を超えるためすべて0個。
のように3の倍数の個数は、3の指数が1ずつ減っていくことが分かる。
よって、素因数3の個数は、\(\small \small 3^{5}+3^{4}+3^{3}+3^{2}+3+1=364\)個となるため、364回割り切れる…【答】.
【補足】等比数列の和の公式を利用した別解
数Ⅱで学習する等比数列の和の公式
$$\small \displaystyle \sum_{k=1}^n ar^{k-1}=\frac{a(r^n-1)}{r-1}$$
を利用すると、\(\small a=1 ,r=3, n=6\)の場合に該当するので
\begin{split}
&\small 1+3+3^2+3^3+3^{4}+3^{5}\\
&\small =\frac{3^{6}-1}{3-1}\\
&\small =\frac{728}{2}\\
&\small =364\\
\end{split}
のように求めることができる。
【応用問題3】\(\small n\)進法表記での末尾の0の個数
（3）\(\small 20!\) を\(\small 3\)進法で表したとき、末尾に連続して並ぶ\(\small 0\)の個数を求めよ。
・10進数では10倍すると末尾に0が1つ増えたので10がいくつ作れるかを確認していたが、3進数の場合は3倍すると末尾に0が1つ増えるので3がいくつ含まれるかを確認できればよい。
例：10進数の「3」は、3進数では\(\small 10_{(3)}\)。
10進数の「3」を3倍した「9」は、3進数では\(\small 100_{(3)}\)。
☞ 3倍すると3進数の末尾に0が1個増える。
・「3がいくつ含まれるか」を求めるということは、結局本問は\(\small 20!\)に含まれる素因数3の個数を求める問題に帰着する。
各桁が\(\small n^m\)で表されるとは？？
『\(\small 120\)』と表される数を10進法と3進法の場合で各桁ごとに分解してみよう。
10進法として各桁ごとに分解すると…
\begin{split}
\small 120_{(10)} &\small = 0+20+100\\
&\small = 0\cdot \color{#ef5350}{10^0}+2\cdot \color{#ef5350}{10^1}+1\cdot \color{#ef5350}{10^2}
\end{split}
のように各桁が\(\small 10^m\)の形に分解できる。
3進法として各桁に分解すると…
$$\small 120_{(3)}=0\cdot \color{#ef5350}{3^0}+2\cdot \color{#ef5350}{3^1}+1\cdot \color{#ef5350}{3^2}$$
のように各桁が\(\small 3^m\)の形に分解できる。
3進法表記した場合の末尾の0の個数を求めたい場合、\(\small 20!\)に含まれる素因数3の個数を求めればよい [*1]。
*1：【補足】\(\small n\)進法と末尾の0の個数
たとえば、10進法で『90』と表記される数を3進法で表記する場合、末尾に0が何個並ぶかを確認してみよう。
『90』を3進法に直すと、
\begin{split}
\small 90_{(10)} &\small = 9+81\\
&\small = 0\cdot \color{#ef5350}{3^0}+0\cdot \color{#ef5350}{3^1}+1\cdot \color{#ef5350}{3^2}+0\cdot \color{#ef5350}{3^3}+1\cdot \color{#ef5350}{3^4}\\
&\small = 10100_{(3)}\\
\end{split}
となるので、末尾には0が2個並ぶことが分かる。これは、10進法の『90』が\(\small 9\)の倍数（\(\small 3^2\)の倍数）だからである。10進法で\(\small 27 (3^3)\)の倍数であれば、3進法表記した際の末尾の0の個数は3個になる（各自確認してみよう）。
つまり、一般に10進法で\(\small 3^n\)の倍数となる数を3進法表記すると末尾の0の個数は\(\small n\)個になることが分かる。
よって、1～20に含まれる\(\small 3^n\)の倍数の個数を求めればよいので
\(\small 3^n\)の倍数の個数
・\(\small 3\)の倍数の個数 ⇒\(\small 20÷3 \space ⇒ 6\)個
・\(\small 3^2\)の倍数の個数 ⇒\(\small 20÷9 ⇒ 2\)個
・\(\small 3^{3}\)の倍数以降は\(\small 20\)を超えるためすべて0個。
よって、素因数\(\small 3\)の個数は \(\small 6+2=8\)個となるため、\(\small 20!\)は\(\small 3^8\)の倍数となる。
ゆえに、3進法で表記したときの末尾の0の個数は8個…【答】.
本記事のまとめ
今回は階乗に含まれる素因数の個数を求める問題とその応用問題について解説してきました。様々なパターンの問題がありましたが、聞かれ方が異なっているだけで考え方自体は共通していることが実感できたのではないでしょうか？
この分野は、考え方をしっかり理解してしまえば応用的なパターンでも解けてしまうので、最後にポイントをしっかり整理しておきましょう。
☆重要ポイント☆
≫素因数の個数の求め方
・\(\small n!\)に含まれる素因数\(\small p\)の個数は1～\(\small n\)に含まれる\(\small p^n\)の倍数の合計数。
数式化するならば、
\begin{split}
&\small \color{#ef5350}{\left(\frac{n}{p}の整数部分\right)+\left(\frac{n}{p^2}の整数部分\right)}\\
&\small \color{#ef5350}{\quad +\left(\frac{n}{p^3}の整数部分\right)+ \cdots}\\
\end{split}
≫解法の指針と問題パターン
≪解法の指針≫
『素因数の個数の求め方』を用いて解けばOK！
≪問題パターン≫
・同じ素数\(\small p\)で割り切れる回数を求める問題【基本問題1】【応用問題2】
⇒素因数\(\small p\)がいくつ含まれるかの問題に帰着
・\(\small p\)進数で表したときの末尾の0の個数を求める問題【応用問題3】
⇒素因数\(\small p\)がいくつ含まれるかの問題に帰着
・末尾の0の個数を求める問題【基本問題2】【応用問題1】
⇒素因数5がいくつ含まれるかを求める問題に帰着
今回は以上です。お疲れさまでした！
コメント