【基本】素因数分解と約数の個数

ここでは、素因数分解を用いて、約数の個数を簡単に数える方法について見ていきます。

【広告】

約数を素因数分解してみる

小学校のときに約数を学んだとき、約数の個数を数える問題を解いたことがあったと思います。もう一度、ここで振り返ってみましょう。

$90$ の正の約数がいくつあるかを考えます。小さい方から順番に書き出すと
\begin{eqnarray}
& & 1,\ 2,\ 3,\ 5,\ 6,\ 9, \\[5pt] & & 10,\ 15,\ 18, \\[5pt] & & 30,\ 45,\ 90 \\[5pt] \end{eqnarray}となり、12個であることがわかります。

今までであれば、このように書くしかなかったわけですが、あまり芸がないです。ここでは、上の約数を素因数分解してみましょう。
\begin{eqnarray}
& & 1,\ 2,\ 3,\ 5,\ 2\times 3,\ 3^2,\ \\[5pt] & & 2\times 5,\ 3\times 5,\ 2\times 3^2, \\[5pt] & & 2\times 3\times 5,\ 3^2\times 5,\ 2\times 3^2\times 5 \\[5pt] \end{eqnarray}元の数は、 $2\times 3^2\times 5$ です。この約数なので、約数を素因数分解したときにも、 $2,3,5$ の素因数しか出てきません。また、もとの数よりも指数が大きくなることはありません。 $2^2$ や $3^3$ などが出てこない、ということです。

素因数分解と約数の個数

正の約数を素因数分解したものは、小さい順に並べるよりも、素因数の種類によって並び替えたほうが見やすくなります。なお、将来学びますが、自然数の0乗は1となります(参考:【基本】整数の指数#ゼロ乗)。これを用いて、先ほどの「正の約数の素因数分解」一覧を、次のように並び替えてみます。
\begin{eqnarray}
2^0\times 3^0\times 5^0,\ 2^0\times 3^1\times 5^0,\ 2^0\times 3^2\times 5^0 \\[5pt] 2^0\times 3^0\times 5^1,\ 2^0\times 3^1\times 5^1,\ 2^0\times 3^2\times 5^1 \\[5pt] \\
2^1\times 3^0\times 5^0,\ 2^1\times 3^1\times 5^0,\ 2^1\times 3^2\times 5^0 \\[5pt] 2^1\times 3^0\times 5^1,\ 2^1\times 3^1\times 5^1,\ 2^1\times 3^2\times 5^1 \\[5pt] \end{eqnarray}上半分と下半分は、素因数 $2$ で分けています。横は、素因数 $3$ によって分けていて、それをさらに縦に素因数 $5$ によって分けています。

上の一覧を見れば、正の約数を $2^x \times 3^y \times 5^z$ と書くと、 $x$ の部分は、 $0,1$ の2通りの場合があり、 $y$ の部分は、 $0,1,2$ の3通りの場合があり、 $z$ は、 $0,1$ の2通りの場合があります。これらにダブりはなく、足りないものもないので、正の約数の個数は\[ 2\times 3\times 2=12 \]個である、ということがわかります。

このことから、素因数分解をすれば、正の約数の個数は簡単に数えられることがわかります。指数(素因数の右上の数)に $1$ を足して、掛け合わせたものが正の約数の個数になる、ということです。書き出さなくても数えられる、という画期的な方法です。

素因数分解と約数の個数
自然数 $N$ を素因数分解すると、 $N=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_n^{a_n}$ となるとき、 $N$ の正の約数の個数は、次の式で表される。\[ (a_1+1)(a_2+1)(a_3+1)\cdots (a_n+1) \]

例えば、 $2^3\times 3^2 \times 7$ も $11\times 13^3 \times 17^2$ も、正の約数の個数は同じで、\[ 4\times 3\times 2=24 \]個となります。この数え方なら、数え漏れをすることもありませんね。

おわりに

ここでは、素因数分解をすれば、正の約数の個数が簡単に数えられる、という話を見てきました。約数を素因数分解してみれば、指数の値が何通りかがわかります。これを利用して個数を数えます。書き出さなくても数えられるようになりましょう。