階乗に含まれる素因数の個数

$n!$ を割り切る $p$ の最大の指数を $[\frac{n}{p}] + [\frac{n}{p ^{2}}] + \dots$ （ $p$ の倍数の個数の和）として求められる

前提

倍数の個数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）

この技能までの道筋（3 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

倍数の個数（算数整数の性質）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）

説明

$n! = 1 \times 2 \times 3 \times \dots \times n$ （ $n$ の階乗）を素因数分解したとき、ある素数 $p$ が何個掛かっているか（ $n!$ を割り切る $p$ の最大の指数）を、実際に $n!$ を計算せずに求められるようになります。 $100!$ の末尾に 0 がいくつ並ぶか、 $n!$ が $2^{k}$ で何回割り切れるか、といった問題で使います。

なぜそうしてよいのか

記号 $[x]$ は「 $x$ 以下の最大の整数」を表すことにします（例: $[3.7] = 3$ , $[5] = 5$ ）。 $1$ から $n$ までの整数のうち $m$ の倍数は $m, 2 m, 3 m, \dots$ と並ぶので、その個数はちょうど $[\frac{n}{m}]$ 個です。

$n!$ に含まれる $p$ の個数は、掛けている各因数 $1, 2, \dots, n$ がそれぞれ $p$ を何個ずつ持っているかの合計です。たとえば $p = 3$ のとき、 $9 = 3^{2}$ は 3 を 2 個、 $27 = 3^{3}$ は 3 を 3 個持っています。そこで、各数が持つ $p$ を「1 個目」「2 個目」「3 個目」…と層に分けて数えます。1 個目の $p$ を持つ数は $p$ の倍数全部で $[\frac{n}{p}]$ 個、2 個目の $p$ を持つ数は $p^{2}$ の倍数で $[\frac{n}{p ^{2}}]$ 個、3 個目を持つ数は $p^{3}$ の倍数で $[\frac{n}{p ^{3}}]$ 個、…となります。 $p^{k}$ でちょうど割り切れる数（ $p$ を $k$ 個持つ数）は、 $p, p^{2}, \dots, p^{k}$ の倍数としてちょうど $k$ 回数えられるので、漏れも重複もありません。

したがって $n!$ を割り切る $p$ の最大の指数は $[\frac{n}{p}] + [\frac{n}{p ^{2}}] + [\frac{n}{p ^{3}}] + \dots$ です。 $p^{j} > n$ になると $[\frac{n}{p ^{j}}] = 0$ なので、和は有限個の項で終わります。ここで $p$ が素数であることが大切で、素数だからこそ「各因数の $p$ の個数を足せば全体の個数になる」と言えます。

手順

素数 $p$ と $n$ を確認し、 $p, p^{2}, p^{3}, \dots$ を $n$ を超えるまで書き出す。
$p^{j} \leq n$ となる各 $j$ について、 $1$ 以上 $n$ 以下の $p^{j}$ の倍数の個数 $[\frac{n}{p ^{j}}]$ （ $n \div p^{j}$ の商）を求める。
それらをすべて足す： $[\frac{n}{p}] + [\frac{n}{p ^{2}}] + \dots$ 。これが $n!$ を割り切る $p$ の最大の指数である。

例題

$50!$ を $3^{k}$ が割り切るような自然数 $k$ の最大値を求めよ。

例題の解答

手順1: $p = 3$ のべきを書き出すと $3, 9, 27, 81$ で、 $81 > 50$ なので $3, 9, 27$ まで考えればよい。

手順2: 各べきの倍数の個数を求める。
$3$ の倍数: $[\frac{50}{3}] = 16$ 個
$9$ の倍数: $[\frac{50}{9}] = 5$ 個
$27$ の倍数: $[\frac{50}{27}] = 1$ 個
（ $81$ の倍数は $[\frac{50}{81}] = 0$ 個）

手順3: 足し合わせて $16 + 5 + 1 = 22$ 。
よって $50!$ は $3^{22}$ で割り切れ、 $3^{23}$ では割り切れない。求める最大値は $22$ 。

答え: $22$

よくある誤り

$p$ の倍数の個数 $[\frac{n}{p}]$ だけを答えてしまう誤り。 $9, 18, 27$ などは 3 を 2 個以上持つので、例えば $50!$ の 3 の指数を $16$ としてはいけない。正しくは $[\frac{50}{3}] + [\frac{50}{9}] + [\frac{50}{27}] = 16 + 5 + 1 = 22$ 。
$\frac{n}{p ^{j}}$ を四捨五入や切り上げしてしまう誤り。倍数の個数は商の整数部分なので、 $[\frac{50}{3}] = 16$ （ $16.6 \dots$ を $17$ にしない）。
素数でない数に公式をそのまま当てはめてしまう誤り。例えば $10!$ を割り切る $4$ の最大の指数を $[\frac{10}{4}] = 2$ とするのは誤り。正しくは 2 の指数 $[\frac{10}{2}] + [\frac{10}{4}] + [\frac{10}{8}] = 5 + 2 + 1 = 8$ を求め、 $4^{k} = 2^{2 k}$ より $2 k \leq 8$ から $k = 4$ 。
末尾の 0 の個数を $[\frac{n}{10}]$ で数えてしまう誤り。 $10 = 2 \times 5$ で、2 は 5 より多く含まれるので 5 の指数で決まる。例えば $100!$ では $[\frac{100}{5}] + [\frac{100}{25}] = 20 + 4 = 24$ 個で、 $10$ ではない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 5（最難関大の二次・数学オリンピック予選レベル）
正の整数 $n$ に対し、 $n!$ が $3^{k}$ で割り切れるような $0$ 以上の整数 $k$ の最大値を $e (n)$ とする。 $1 ≦ n ≦ 500$ を満たす整数 $n$ のうち、 $n - 2 e (n) = 4$ が成り立つものの個数を求めよ。

この技能の次に学べること

p 進付値と p 進収束（大学院数学代数的整数論）