ホーム >> 整数 >> 階乗の素因数の個数



階乗の素因数の個数についての公式

階乗の素因数の個数: $n!$ に含まれる素因数 $p$ の個数は, $$\large \sum_{k=1}^{\infty} \left[\frac{n}{p^k}\right]=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\cdots$$

この公式の意味を順を追って説明していきます.

階乗

自然数 $n$ の階乗とは,$1$ から $n$ までの積 $1\times2\times\cdots\times n$ のことで,これを $n!$ と表します. $$n!=1\times2\times\cdots\times n$$ たとえば, $$3!=1\times2\times3=6$$ $$4!=1\times2\times3\times4=24$$ です.

素因数

素因数とは,素数であるような約数のことです.
たとえば,$10$ の素因数は $2$ と $5$ です. $$10=2\times5$$ なので,$10$ に含まれる素因数 $2,5$ の個数はそれぞれ $1$ つずつあります.一方, $12$ を素因数分解すると, $$12=2^2\times3$$ なので,$12$ は素因数 $2,3$ をもち,$12$ に含まれる素因数 $2$ の個数は $2$ 個,$3$ の個数は $1$ 個です.

ガウス記号とΣ

$[x]$ はガウス記号で,$x$ を超えない最大の整数を表します.たとえば, $$[3]=3,\ \ \left[\frac{1}{2}\right]=0,\ \ [-4.3]=-5,\ \ [\pi]=3,\ \ \left[-\sqrt{5}\right]=-3$$ などが成り立ちます.詳しくは, →ガウス記号の基礎的なこと
左辺の Σ(シグマ) は,$k$ を $1$ から無現大まで足し合わせるという意味ですが,今回の場合は,足し合わせる数は実際には有限個だけ考えればよいです.なぜなら,$k$ が十分大きくなればいずれは $p^k$ が $n$ より大きくなります.すると,$\left[\frac{n}{p^k}\right]=0$ となるので,以降ずっと足し合わせる数は $0$ になるからです.

つまり,$p^N< n$ をみたす最大の自然数を $N$ とすると, $$\sum_{k=1}^{\infty} \left[\frac{n}{p^k}\right]=\sum_{k=1}^{N} \left[\frac{n}{p^k}\right]=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\cdots +\left[\frac{n}{p^N}\right]$$ となります.

$10!$ に含まれる素因数 $2$ の個数は,上の公式を用いると, $$\left[\frac{10}{2}\right]+\left[\frac{10}{2^2}\right]+\left[\frac{10}{2^3}\right]=5+2+1=8$$ より,$8$ 個です.実際,$10!$ をがんばって素因数分解してみると, $$10!=2^8\times3^4\times5^2\times7$$ となるので,確かに $2$ の素因数は $8$ 個であることがわかります.

公式の直感的な説明

公式が成り立つ理由を説明します.一般的な証明を書くのではなく,具体例で説明します.

$n$ 以下の $k$ の倍数の個数

$1$ から $100$ までの自然数のうち,$3$ の倍数はいくつあるでしょうか.$100$ を $3$ で割ると, $$100=33\times 3+1$$ なので,$33$ 個あります.

先の式の両辺を $3$ で割ると, $$\frac{100}{3}=33+\frac{1}{3}$$ したがって, $$\left[\frac{100}{3}\right]=\left[33+\frac{1}{3}\right]=33$$ 以上のことをまとめると一般に次のことが成り立ちます.

$n,k$ を自然数とするとき,次が成り立つ. $$(1 以上 n 以下の k の倍数の個数)= \left[\frac{n}{k}\right]$$

公式の説明

上の事実をふまえた上で, $20!$ に含まれる素因数 $2$ の個数を考えてみましょう.

これは言い換えれば,$20!$ が $2$ で何回割り切れるか,ということです.そこで,$1$ から $20$ までの数を下の表のように書き並べてみます. \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20 \\ \hline 2の倍数&&\bigcirc&&\bigcirc&&\bigcirc&&\bigcirc&&\bigcirc&&\bigcirc&&\bigcirc&&\bigcirc&&\bigcirc&& \\ \hline 4の倍数&&&&\color{red}{\bigcirc}&&&&\color{red}{\bigcirc}&&&&\color{red}{\bigcirc}&&&&\color{red}{\bigcirc}&&&& \\ \hline 8の倍数&&&&&&&&\color{blue}{\bigcirc}&&&&&&&&\color{blue}{\bigcirc}&&&& \\ \hline 16の倍数&&&&&&&&&&&&&&&&\color{green}{\bigcirc}&&&& \\ \hline \end{array}
上で見たように, $1$ 以上 $20$ 以下の自然数のうち,$2$ の倍数の個数は,$\left[\frac{20}{2}\right]=10$ 個あります.
同様にして,$4$ の倍数の個数は,$\left[\frac{20}{4}\right]=5$ 個,$8$ の倍数の個数は,$\left[\frac{20}{8}\right]=2$ 個,$16$ の倍数の個数は,$\left[\frac{20}{16}\right]=1$ 個です.
$20!$ は $1$ から $20$ までの自然数の積ですから,$2$ の素因数の個数は,表の丸印の数だけあります.したがって, $$\left[\frac{20}{2}\right]+\left[\frac{20}{4}\right]+\left[\frac{20}{8}\right]+\left[\frac{20}{16}\right]=10+5+2+1=18$$ $20!$ に含まれる素因数 $2$ の個数は $18$ 個です.

一般の $n$ と素因数 $p$ についても同じことがいえます.つまり,$1$ から $n$ までの自然数について,$p$ の倍数であるもの,$p^2$ の倍数であるもの,$p^3$ の倍数であるものなどの個数をカウントしていけば,$n!$ に含まれる素因数 $p$ の個数が求められます.これを式であらわすと,最初にのべた数式になるということです.

練習問題

具体的な問題で公式の使い方を練習してみましょう.まずは,公式をそのまま使うだけです.

 $50!$ に含まれる素因数 $3$ の個数を求めよ.

→solution

$$\left[\frac{50}{3}\right]+\left[\frac{50}{3^2}\right]+\left[\frac{50}{3^3}\right]=16+5+1=22$$ よって,$22$ 個.

下の問題のように別の聞かれ方をされることもありますが,本質は同じです.

 $100!$ の末尾に $0$ はいくつ並ぶか.

→solution

末尾に $0$ がいくつ並ぶかということは,すなわち,$10$ で何回割り切れるか,ということと同じである.$10=2\times 5$ であり,$100!$ に含まれる $2$ の素因数の個数と,$5$ の素因数の個数を比べると,$5$ の素因数の個数の方が少ない.よって, $$\left[\frac{100}{5}\right]+\left[\frac{100}{5^2}\right]=20+4=24$$ $24$ 個.

 $50!$ を二進法であらわしたとき,末尾に $0$ はいくつ並ぶか.

→solution

二進法であらわしたときに末尾に並ぶ $0$ の数と,$2$ で割り切れる回数は一致する.したがって, $$\left[\frac{50}{2}\right]+\left[\frac{50}{2^2}\right]+\left[\frac{50}{2^3}\right]+\left[\frac{50}{2^4}\right]+\left[\frac{50}{2^5}\right]=25+12+6+3+1=47$$ よって,$47$ 個.

一番最初の節で,公式が成り立つことを素因数分解によって確かめましたが,逆に,この公式を用いて階乗の数をすばやく素因数分解することができます.

 $20!$ を素因数分解せよ.

→solution

$20$ 以下の素数は,$2,3,5,7,11,13,17,19.$ それぞれについて,$20!$ に含まれる素因数の個数を公式を用いて計算すると, $17,8,4,2,1,1,1,1$ である.よって,$20!$ を素因数分解すると, $$2^{17}\times 3^{8}\times 5^{4}\times 7^{2}\times11\times 13\times17\times19$$

最後の問題は,$2009$ 年京都大学入試の類題です.

 $p$ を素数とする.$(p^2)!$ は $p$ で何回割り切れるか.

→solution

$$\left[\frac{p^2}{p}\right]+\left[\frac{p^2}{p^2}\right]=p+1$$ よって,$p+1$ 回割り切れる.