約数の個数の公式と平方数の性質

例えば $12$ を素因数分解すると $2^2\cdot 3$ です。 $2$ の指数を ${0,1,2}$ の中から一つ，$3$ の指数を ${0,1}$ の中から一つ選ぶと約数が決まります。

よって約数の個数は $3\times 2=6$ 個です。

$n$ の約数について考える。素因数分解された形を $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ とする。 $n$ の約数は $p_1^{b_1} p _2^{b_2}\cdots p_k^{b_k}$ （ただし，各 $i$ に対して $b_i$ は $0\leq b_i\leq a_i$ を満たす整数，$p_i$ は素数）という形の整数だけであり，これで全ての約数を表せる。

そのような $b_i$ の選び方は

$(a_1+1)(a_2+1)\cdots (a_k+1)$

通りである。

つまり，約数の個数は「素因数分解して」「それぞれの指数に1を足して」「全部かけあわせる」と計算できる。

$n=p_1^{a_1} p _2^{a_2}\cdots p_k^{a_k}$ と素因数分解されているとき，$n$ が平方数であるというのは，平方数の定義より $a_1,\:a_2,\cdots,\:a_k$ がいずれも偶数であることと同値。

一方，$n$ の約数の個数が奇数であるというのは，約数の個数の公式より $(a_1+1)(a_2+1)\cdots (a_k+1)$ が奇数であることと同値。

これは $a_1,\:a_2,\cdots,\:a_k$ がいずれも偶数であることと同値。

$m$ が $n$ の約数のとき，$\dfrac{n}{m}$ も $n$ の約数である。このことに注意すると，$n$ の約数を小さい順に $1=d_1,\:d_2,\cdots, d_N=n$ と並べたとき，$d_1d_N=n,\:d_2d_{N-1}=n$ などが成立する。つまり，大きい方と小さい方から一つずつとってくるとかけて $n$ になるペアができる。

$n$ が平方数のときは $m=\dfrac{n}{m}$ となる約数 $m$ が存在するので真ん中で一つ余る。それ以外は全てペアになる。よって約数の個数は奇数。

$n$ が平方数でないときは $m=\dfrac{n}{m}$ となる正の整数 $m$ が存在しないので，全てペアになる。よって約数の個数は偶数。