【標準】素因数分解と何回割れるか問題

🕒 2018/07/19 🔄 2023/05/01

ここでは、ある数が素数で何回割れるか、という問題について考えます。

📘 目次

何回割れるか

例題

$k$ は自然数とします。
(1) $10!$ が $5^k$ で割り切れるとき、 $k$ の最大値を求めなさい。
(2) $10!$ が $3^k$ で割り切れるとき、 $k$ の最大値を求めなさい。
(3) $10!$ が $2^k$ で割り切れるとき、 $k$ の最大値を求めなさい。

$10!$ というのは、 $10$ の階乗のこと（参考：【基本】順列）で、 $1$ から $10$ までの自然数をすべて掛け合わせたものです。

実際に計算すると、 $10!=3628800$ となります。これを実際に割っていく、という方法もありえますが、面倒です。そもそも、 $5$ で割り切れるかどうかは、 $10!$ の中に素因数 $5$ がいくつ含まれているかを数えればよく、他の素因数についてはどうでもいいので、すべてを掛け合わせる必要はありません。

$10$ までの自然数の中に、5の倍数が $5$, $10$ の2つが入っています。他の数は5の倍数ではないので、 $10!$ は $5^2$ で割れて、 $5^3$ では割れないことがわかります。よって、(1)の解は、 $k=2$ です。

(2)も同様に考えると、 $10$ までの自然数の中に3の倍数が3つあるから、 $3^3$ で割り切れることがわかります。しかし、(1)とは異なり、 $3^4$ でも割れてしまいます。実際に確かめてみると、 $10!$ を $3^3$ で割ったときの商は、 $134400$ で、さらに $3$ で割れてしまいます。

なぜこういうことが起こるかというと、「3の倍数がいくつあるか」を数えていたところがまずかったんですね。3の倍数というのは、 $3,6,9$ の3つがありますが、 $9$ は $3$ で2回割れます。だから、 $3\times 6\times 9$ は $3$ で4回割ることができ、 $10!$ は $3^4$ で割れることがわかります。他に素因数 $3$ を含むものはないので、 $3^5$ では割り切れず、(2)の解は $k=4$ となります。

最後の(3)を考えましょう。同じように考えれば、まず $10$ までの自然数の中に、2の倍数が5個あることがわかります。 $2,4,6,8,10$ の5つです。それぞれ、2で何回割れるかを数えると、回数は、 $1,2,1,3,1$ となります。合計すると、 $10!$ は $2^8$ で割り切れることがわかります。他に2の素因数がないので、 $2^9$ では割り切れず、(3)の解は $k=8$ となります。

実際、 $10!$ を $2^8$ で割ると、 $14175$ となり、これ以上2で割り切ることができないことがわかります。

何回割れるかをどう数えるか

先ほど、 $10!$ が $3$ で何回割れるかを考えました。これを考えるときに、 $10!$ の積に出てくる各数字が、 $3$ で何回割れるかに注目しました。3の倍数以外は3で割り切れることはありません。3の倍数のうち、 $3,6$ は1回ずつ、 $9$ は2回割り切れるから、合わせて4回割れる、5回は割れない、ということがわかりました。

ただ、このような数え方だと、数字が大きくなってきたときに大変です。 $50!$ が3で何回割れるか、を考えるときに、各数字が3で何回割れるかを数えて、回数を足し合わせる、というのは面倒です。もう少し簡単に求めたいですね。

そこで、パターンを把握するために、先ほどの問題の(3)を考えなおしましょう。 $1$ から $10$ までの数字が、 $2$ で何回割れるかを一覧にしてみました。

	$2^1$ で割れる	$2^2$ で割れる	$2^3$ で割れる
1	-	-	-
2	○	-	-
3	-	-	-
4	○	○	-
5	-	-	-
6	○	-	-
7	-	-	-
8	○	○	○
9	-	-	-
10	○	-	-

上の問題では、各行の丸の数を数えたことに対応します。 $1+2+1+3+1=8$ という感じですね。しかし、横に足すよりも、縦に足した方が簡単でしょう。左の列は〇が5個ありますが、これは2つに1つが該当するので、 $10\div 2^1=5$ と出せます。真ん中の列は〇が2個ですが、これは $10\div 2^2=2.5$ だから2個と出せます。 $10\div 2^3=1.25$ だから、右端は1個です。よって、 $5+2+1=8$ となります。

このように、素因数の $n$ 乗で割り切れるものが何個あるかを数えたほうが簡単です。

このことを踏まえて、 $50!$ が $3^k$ で割り切れる場合を考えてみましょう。 $50$ までの中に、 $3^n$ で割れるものが何個あるかを数えるには、
\begin{eqnarray} 50\div 3^1 &=& 16.\cdots \\ 50\div 3^2 &=& 5.\cdots \\ 50\div 3^3 &=& 1.\cdots \\ \end{eqnarray}を計算すればよく、これらから、 $3^k$ で割りきれるような $k$ の最大値は、\[ 16+5+1=22 \]となることがわかります。