【定理・公式・証明】高校数学定理・公式 – 数学A – 自然数の積と素因数の個数

自然数の個数と素因数の個数

$n!$ が $n!=p^a q^b \cdots$ と素因数分解できるとき，

$a=(n 以下のpの倍数の個数)+(n以下のp^2 の倍数の個数)+ \cdots$

$b=(n以下のqの倍数の個数)+(n以下のq^2 の倍数の個数)+ \cdots$

説明

例えば， $16!$ を素因数分解したときの，素因数 $2$ の個数について考える。

票の〇は，16以下のそれぞれの自然数の持つ素因数 $2$ の個数を，縦に〇を積むことで表している。〇の数は全部で15個あるから， $16!$ を素因数分解すると，素因数2の個数は15となる。(つまり， $16!=2^15 \cdot 3^b \cdot \cdots$ と素因数分解できる)

さて，この表の〇を横に数えてみる。

一番下の行は， $2$ の倍数 $(2,4,6, \cdots ,16)$ のところに合計8個の〇がついている。

下から2行目は， $2^2$ の倍数 $(4,8,12,16)$ のところに合計4個の〇がついている。

下から3行目は， $2^3$ の倍数 $(8,16)$ のところに合計2個の〇がついている。

一番上の行は， $2^4$ の倍数 $(16)$ のところに1個の〇がついている。

よって，

$15=8+4+2+1$

すなわち，

$(16! を素因数分解したときの素因数2の個数)$

$＝(16以下の自然数における2の倍数の個数)+(16以下の自然数における 2^2 の倍数の個数)+(16以下の自然数における 2^3 の倍数の個数)+(16以下の自然数における 2^4 の倍数の個数)$

が成り立つ。16以下の自然数では， $(2^5 の倍数の個数)=(2^6の倍数の個数)= \cdots =0$ であるから， $2^4$ の倍数の個数まで調べれば十分である。

一般に， $n!$ を素因数分解したときの素因数 $p$ の個数を求めるときは，

$p^m \leqq n \lt p^{m+1}$ を満たすような整数 $m$ について， $n$ 以下の $p,p^2 , \cdots p^m$ の倍数の個数をそれぞれ調べ，和をとればよい。