【標準】素因数分解と約数の和
ここでは、約数の和を求める問題を見ていきます。
約数を素因数分解してみる
【基本】素因数分解と約数の個数では、約数を素因数分解することで、個数を簡単に求める方法を見ました。ここでも、約数を素因数分解して考えてみましょう。
$250=2\times 5^3$ なので、約数は $2^x\times 5^y$ と書けます。ここで、 $x=0,1$ で、 $y=0,1,2,3$ です。なお、 $2^0=5^0=1$ です。約数は全部で8個、ということがわかります。
これらを全部足すのですが、次のように因数分解できます。
\begin{eqnarray}
& & 2^0\times 5^0+2^0\times 5^1+2^0\times 5^2+2^0\times 5^3 \\
& &+2^1\times 5^0+2^1\times 5^1+2^1\times 5^2+2^1\times 5^3 \\[5pt]
&=&
2^0(5^0+5^1+5^2+5^3) \\
& & +2^1(5^0+5^1+5^2+5^3) \\
&=&
(2^0+2^1)(5^0+5^1+5^2+5^3) \\
\end{eqnarray}これを見ると、 $2^x$ で $x=0,1$ のときの和を計算し、 $5^y$ で $y=0,1,2,3$ のときの和を計算し、掛ければ答えになる、ということがわかります。こうした方が、計算が楽になりますね。\[ 3\times 156=468 \]と和が求められます。
素因数が3種類の場合
今度は、 $90=2^1\times 3^2\times 5^1$ なので、素因数が3種類です。【基本】素因数分解と約数の個数で見たときと同じです。このときの和も、因数分解できるのではないか、という観点で計算していきましょう。
\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 \\
& & +2^0\times 3^0\times 5^1 +2^0\times 3^1\times 5^1 +2^0\times 3^2\times 5^1 \\
& & +2^1\times 3^0\times 5^0 +2^1\times 3^1\times 5^0 +2^1\times 3^2\times 5^0 \\
& & +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]
&=&
(2^0+2^1) \\
& & \times (3^0\times 5^0 +3^1\times 5^0 +3^2\times 5^0 \\
& & \quad +3^0\times 5^1 +3^1\times 5^1 +3^2\times 5^1) \\[5pt]
&=&
(2^0+2^1)(3^0+3^1+3^2)(5^0+5^1) \\[5pt]
\end{eqnarray}これを見ると、 $2^x$ で $x=0,1$ のときの和を計算し、 $3^y$ で $y=0,1,2$ のときの和を計算し、 $5^z$ で $z=0,1$ のときの和を計算し、それらの積を計算すれば答えになることがわかります。よって、\[ 3\times 13 \times 6=234 \]となります。
すこし慣れないとわかりにくいですが、\[ (2^0+2^1)(3^0+3^1+3^2)(5^0+5^1) \]を展開したときの各項がどうなるかを考えてみましょう。1つ目のカッコ、2つ目のカッコ、3つ目のカッコからどの項を選んで展開するかによって、 $2^x\times 3^y\times 5^z$ の指数が変わってきます。すべて展開すると、 $90$ の正の約数が1回ずつ出てくるので、上の式を計算すれば正の約数の和が計算できることになります。
これは、素因数が増えても同じで、一般的な内容でまとめると次のようになります。
\begin{eqnarray} & & (1+p_1+p_1^2+\cdots +p_1^{a_1}) \\ & & \times (1+p_2+p_2^2+\cdots +p_2^{a_2}) \\ & & \times \cdots \\ & & \times (1+p_n+p_n^2+\cdots +p_n^{a_n}) \\ \end{eqnarray}
因数分解ができるから、それぞれの素因数の場合を計算して掛ければいい、という発想は、知っていないとなかなか思いつかないですね。
おわりに
ここでは、正の約数の和を求める問題を見ました。すべてを素直に足し合わせるよりも計算が楽になることが多いので、因数分解を使う方法で求められるようになりましょう。
