ホーム >> 整数 >> 約数の個数の求め方

約数の個数の求め方を紹介します.




素数とそのベキの約数の個数

まずは簡単な数から考えてみましょう.素数は $1$ と自分自身以外に約数をもたない数なので,素数の約数の個数は常に $2$ 個です.

つぎに,素数 $p$ を用いて $p^k$ と表される数を考えてみましょう.つまり,ある素数のべき乗の形になっている数です.たとえば,$8,9,125,1024$ などが考えられます.$p^k$ の約数は小さい方から順に, $$1,p,p^2,p^3,\cdots,p^{k-1},p^k$$ であるから,約数の個数は $k+1$ 個です.

約数の個数の求め方

さて,別の素因数が増えたときはどのように考えればよいでしょうか.たとえば,$28=2^2\times 7$ の約数は,$1,2,4,7,14,28$ で,合計 $6$ 個ですが,これは次のような表を見るとよりわかりやすいです.
\begin{array}{c|ccc} &2^0&2^1&2^2 \\ \hline 7^0&1&2&4 \\ 7^1&7&14&28 \end{array} 横に $2^2$ の約数を並べ,縦に $7$ の約数を並べ,表には縦と横の数の積が書かれています.すると,表内には, $28$ の約数がひとつずつ現れます.つまり,$28$ の約数というのは,$2^0,2^1,2^2$ から一つを選び,さらに $7^0,7^1$ から一つ選びそれらの積で表せるということです.$2^0,2^1,2^2$ から一つ選ぶ選び方が $3$ 通りで,$7^0,7^1$ から一つ選ぶ選び方が $2$ 通りなので,$28$ の約数の個数は $6$ 個ということになります.

一般に,$n=p^kq^s$ の約数は $p^xq^y (0 \le x \le k,0 \le y \le s)$ という形をしています.したがって,$n$ の約数の個数は,($x$ の選び方) $\times$ ($y$ の選び方) $=(k+1)(s+1)$ となります.これは,$k+1$ 人の男と $s+1$ 人の女からひとりずつ選んでペアをつくる場合の数と同様の考え方です.

さらに素因数が増えても同様の考え方により,約数の個数は次の式で表されます.

約数の個数の公式: 整数 $n$ が,$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ と素因数分解されるとき,$n$ の約数の個数は以下の式で表される. $$(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$$

この式の意味は,整数を素因数分解することができれば,その約数の個数が簡単に求まるということです.

平方数と約数の個数の偶奇

平方数と約数の個数には次のような深い関係があります.

$n$ が平方数 ⇔ $n$ の約数の個数が奇数

証明: $n$ を素因数分解表示する.$n$ は相異なる素数 $p_1,...,p_k$ と負でない整数 $\alpha_1,...,\alpha_k$ を用いて, $$n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$ と書ける.このとき,$n$ の約数の個数は, $$(\alpha_1+1)(\alpha_2+1) \cdots (\alpha_k+1)$$ である.$n$ が平方数なら $\alpha_1,...,\alpha_k$ はすべて偶数なので,$n$ の約数の個数は奇数となる.逆も当然成り立つ.

以上,踏まえた上で興味があれば次の平方数と約数の個数に関する問題を解いてみてください.
→ロッカーの開け閉め


$n$ が平方数 ⇔ $n$ の約数の個数が奇数 という事実はわりとよく使います.