## 概要

2つの整数 $a,b$ があり、$a$ が $b$ で割り切れるとき、 $b$ を $a$ の約数という。ちなみに、$a$ は $b$ の倍数という。

例えば $4$ は $36$ の約数。

ある数の **約数の総和（全ての約数を足した値）** は、素因数分解して、素数のブロックの中で約数を足し合わせたものをかけることで、求めることができる。

## 例

$180$ を素因数分解すると、$180 =2^2\times3^2\times5$ となるので、$180$ の約数の総和は、

$$(2^0+2^1+2^2)(3^0+3^1+3^2)(5^0+5^1)=546$$

と求めることができる。これはすなわち、$180$ の約数

$$
\begin{align} 
&1,2,3,4,5,6,9,10,12,15,18,\\\\
&20,30,36,45,60,90,180
\end{align} 
$$

を足した値となっている。（時間が有り余っている人は計算してみよう）

### 補足

なぜこの式で答えが出るかを、上の例で証明すると、$180$ の約数については、

素因数 $2$ の使い方が $2+1$ 通り：

$$2^0,2^1,2^2$$

素因数 $3$ の使い方が $2+1$ 通り：

$$3^0,3^1,3^2$$

素因数 $5$ の使い方が $1+1$ 通り：

$$5^0,5^1$$

その掛け合わせた組み合わせが約数となるので、約数の個数は

$$(2+1)(2+1)(1+1)=18\text{ 個}$$

ある。ここで、上の求めた式

$$(2^0+2^1+2^2)(3^0+3^1+3^2)(5^0+5^1)$$

を展開してみると、$18$ 個の項の一つ一つが、上の組み合わせた $18$ 個の約数になっていて、それらが足される形が出てくることが確認できる。

約数の総和

概要

例

補足

タグ