divisor

<h2>約数の数と総和</h2>

まず、具体的な数 \(360\) で考える。以下、約数は正の約数とする。


 \(360 = 2^3\cdot 3^2\cdot 5^1\) と素因数分解できる。


素因数 \(2\) の取り出し方は \(0, 1, 2, 3\) の \(3+1\) 通り。 
素因数 \(3\) の取り出し方は \(0, 1, 2\) の \(2+1\) 通り。 
素因数 \(5\) の取り出し方は \(0, 1\) の \(1+1\) 通り。 
よって、約数の数はこれらの積
\[
(3+1)(2+1)(1+1) = 24
\]
素因数 \(2\) による約数の総和は \(2^0+2^1+2^2+2^3\)。 
素因数 \(3\) による約数の総和は \(3^0+3^1+3^2\)。 
素因数 \(5\) による約数の総和は \(5^0+5^1\)。 
よって、約数の総和はこれらの積
\[(2^0+2^1+2^2+2^3)(3^0+3^1+3^2)(5^0+5^1) = 1170\]


次に一般化して示す。\(p_i\) を素数として \(\prod_{i=1}^{m}p_i^{k_i}\) と素因数分解できる数 \(n\) において、 
約数の個数 \(d(n)\) は：
\[
\begin{gathered}
d(n) = (k_1+1)(k_2+1)\cdots(k_{m-1}+1)(k_m+1)\\
= \prod_{k=1}^{m}(k_i+1)\\
\end{gathered}
\]
約数の総和は \(\sigma(n)\)：
\[
\begin{gathered}
\sigma(n)
= (p_1^0+p_1^1+\cdots+p_1^{k_1})\cdots(p_m^0+p_m^1+\cdots+p_m^{k_m})\\
= \left(\sum_{j=0}^{k_1}p_1^j\right)\left(\sum_{j=0}^{k_2}p_2^j\right)\cdots\left(\sum_{j=0}^{k_{m-1}}p_{m-1}^j\right)\left(\sum_{j=0}^{k_m}p_m^j\right)\\
= \prod_{i=1}^{m}\left(\sum_{j=0}^{k_i}p_i^j\right)
\end{gathered}
\]
また、\(\sum_{j=0}^{k_i}p_i^j\) は初項 \(1\) 公比 \(p_i\) 項数 \(k_i+1\) の等比級数 \(\frac{p_i^{k_i+1}-1}{p_i-1}\) により以下のようにも表せる。
\[
\begin{gathered}
\sigma(n)
= (1+p_1^1+\cdots+p_1^{k_1})\cdots(1+p_m^1+\cdots+p_m^{k_m})\\
= \left(\frac{p_1^{k_1+1}-1}{p_1-1}\right)\left(\frac{p_2^{k_2+1}-1}{p_2-1}\right)\cdots\left(\frac{p_{m-1}^{k_{m-1}+1}-1}{p_{m-1}-1}\right)\left(\frac{p_m^{k_m+1}-1}{p_m-1}\right)\\
= \prod_{i=1}^{m}\left(\frac{p_i^{k_i+1}-1}{p_i-1}\right)
\end{gathered}
\]


以下の性質をあげることができる。
<ol>
<li>\(d(n)\) が奇数になるのは \(n\) が平方数のときのみである。</li>
<li>\(\sigma(n)\) が奇数になるのは \(n\) が平方数または平方数の２倍のときのみである。</li>
</ol>
平方数とは \(k_i\) がすべて偶数であるような \(n\) である。


<ol>
<li>\(d(n) = \prod_{k=1}^{m}(k_i+1)\) が奇数であるとき、\(k_i+1\) はすべて奇数である。すると \(k_i\) はすべて偶数であるので、\(n=\prod_{i=1}^{m}p_i^{k_i}\) は平方数である。この逆もまた真となる。</li>
<li>\(\sigma(n) = \prod_{i=1}^{m}\left(\sum_{j=0}^{k_i}p_i^j\right)\) が奇数であるとき、\(\sum_{j=0}^{k_i}p_i^j\) はすべて奇数である。すると、\(\sum_{j=1}^{k_i}p_i^j\) はすべて偶数である。そのような \(k_i\) は \(p_1\neq 2\) の素数ならばすべて偶数のとき（つまり平方数）であり、\(p_1=2\) の素数のときは \(k_1\) のみが奇数で他すべて偶数のとき（平方数の２倍）である。この逆もまた真となる。</li>
</ol>