자연수에 있어서 약수의 개수와 약수의 총합
자연수의 “양의 약수”의 개수와 총합을 구하기
정리
자연수 \(N = p^l \times q^m(p, q는 서로 다른 소수, l, m은 음이 아닌 정수)\)에 대하여,
- \(N\)의 양의 약수의 개수 : \((l + 1)(m + 1)\)
- \(N\)의 양의 약수의 총합: \((1 + p + p^2 + \cdots p^l)(1 + q + q^2 + \cdots + q^m)\)
설명
양의 약수의 개수
\(N\)이 \(12\)일 때, \(N = 2^2 \times 3^1\)이다.
이때, \(2^2\)는 \(2^0\)부터 \(2^2\) 총 3가지 경우의 수가 있고, \(3\)은 \(3^0\), \(3^1\), 2가지 경우의 수가 있다. 이들을 조합해서 만들 수 있는 약수는 \(3 \times 2\), 6가지다.
\(l = 2\), \(m = 1\)일 때, \((2 + 1)(1 + 1) = 6\)이다.
양의 약수의 총합
\(N\)이 \(12\)일 때를 다시 보자. \(N = 2^2 \times 3^1\)이므로, 약수의 개수는 (위에서 구한 것처럼) 총 6개이다. 모든 약수의 합은 다음처럼 구할 수 있다.
\[(2^0 \times 3^0) + (2^1 \times 3^0) + (2^2 + \times 3^0) + (2^0 \times 3^1) + (2^1 \times 3^1) + (2^2 + \times 3^1) \\ \quad \\ = 3^0(2^0 + 2^1 + 2^2) + 3^1(2^0 + 2^1 + 2^2) \\ \quad \\ = (3^0 + 3^1)(2^0 + 2^1 + 2^2) \\ \quad \\ = (1 + 3^1)(1 + 2^1 + 2^2)\]