🏠 Home / 数学A / 整数の性質 / 約数と倍数

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

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

📘 目次

何回割れるか

例題
$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 \]となることがわかります。

おわりに

ここでは、ある階乗が、ある素数で何回割れるかを数える問題を見ました。素数の $n$ 乗で割れるものが何個あるかに注目すると数えやすくなることを理解しておきましょう。

関連するページ

YouTubeもやってます

チャンネル登録はコチラから (以下は、動画のサンプルです)
東北大学2024年度後期数学文理共通第4問 横浜国立大学文系2024年度後期数学第1問 奈良女子大学理学部2024年度数学第1問 成城大学経済学部2024年度A方式1日目数学第3問 一橋大学2024年度後期数学第5問1 近畿大学医学部2024年度後期数学第3問