正の整数の約数の個数と総和を求める方法

正の整数の約数の個数と総和を求める方法についてまとめます。

以下、正の整数Aが
\(A = p^kq^lr^m\)と素因数分解されるとします。

正の約数の個数を求める公式は以下のようになります。

\((k + 1)(l + 1)(m + 1)\)個

正の整数12を基準に考えてみます。

12を素因数分解すると

\(12 = 2^2 \times 3\)だから、正の約数は

\(2^a \times 3^b(a = 0,1,2:b = 0,1)\)

で表されるので、組(a,b)のとり方だけ約数があります。

aは0,1,2の3通り、bの決め方は0,1の2通りなので、
積の法則より、正の約数の個数は、

\(3 \times 2 = 6\)個になります。

正の約数の総和を求める公式は以下のようになります。

\((1 + p + \cdot \cdot \cdot + p^k)(1 + q + \cdot \cdot \cdot + q^l)(1 + r + \cdot \cdot \cdot + r^m)\)

\(12 = 2^2 \times 3^1\)の正の約数の総和は

\(2^0 \cdot 3^0 + 2^0 \cdot 3^1 + 2^1 \cdot 3^0 + 2^1 \cdot 3^1 + 2^2 \cdot 3^0 + 2^2 \cdot 3^1\)

\(= 2^0(3^0 + 3^1) + 2^1(3^0 + 3^1) + 2^2(3^0 + 3^1)\)

この式をまとめると、(\(2^2\)の正の約数の和) × (\(3^1\)の正の約数の和)という形に変形することができます。

\(= (2^0 + 2^1 + 2^2)(3^0 + 3^1) = (1 + 2 + 2^2)(1 + 3)\)

上式を計算することで、正の約数の和が計算できることになります。

初版:2021/8/30

Tweet