약수의 개수, 약수의 합

(출처: https://cp-algorithms.com/algebra/divisors.html)

 

어떤 자연수 \(n\)의 약수의 개수를 \(d(n)\), 약수의 합을 \(\sigma(n)\)이라고 할 때 각각을 구하는 방법을 알아보겠습니다.

소인수 분해(prime factorization)를 활용합니다.

 

 

약수의 개수(Number of divisors) 구하는 법

n의 약수 d를 소인수분해하면 n을 소인수분해 한 것의 부분 집합이라는 것은 자명합니다. 예를 들어 \(6=2 \cdot 3\)은 \(60=2^2 \cdot 3 \cdot 5\)의 약수입니다. 따라서 우리는 n의 소인수분해의 모든 부분집합을 구하면 됩니다.

x개의 원소가 있는 집합의 부분집합의 개수는 \(2^x\)개입니다. 단, 집합에 한 원소가 여러번 나타나면 이 공식은 성립하지 않습니다. n을 소인수분해했을 때 어떤 소수는 여러번 곱해질 수 있습니다

n을 소인수분해했을 때 어떤 소수 p가 e번 나타난다고 하면, 부분집합에 p가 e번까지 나타날 수 있다는 것을 알 수 있습니다. 여기서 e+1개의 경우의 수가 생기는 것을 알 수 있습니다.

따라서 n을 소인수분해하면 \(p_i\)가 서로 다른 소수라고 했을 때 \(p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\)이고, 이때 약수의 개수는 다음과 같습니다.

\[d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)\]

 

소인수가 1개, 2개일 때를 생각해 봅시다.

• 소인수가 1개일 때, \(n=p_1^{e_1}\), \(e_1 + 1\)개의 약수가 존재하는 것은 명확합니다.
  \((1, p_1 , p_1^2 , \dots , p_1^{e_1} )\)
• 소인수가 2개일 때, \(n = p_1^{e_1} \cdot p_2^{e_2}\), 따라서 아래 표처럼 약수들을 만들 수 있습니다
  \begin{array}{c|ccccc} & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\ \hline 1 & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\ p_1 & p_1 & p_1 \cdot p_2 & p_1 \cdot p_2^2 & \dots & p_1 \cdot p_2^{e_2} \\ p_1^2 & p_1^2 & p_1^2 \cdot p_2 & p_1^2 \cdot p_2^2 & \dots & p_1^2 \cdot p_2^{e_2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ p_1^{e_1} & p_1^{e_1} & p_1^{e_1} \cdot p_2 & p_1^{e_1} \cdot p_2^2 & \dots & p_1^{e_1} \cdot p_2^{e_2} \\ \end{array}
  이때의 약수의 개수는 \((e_1 +1)\cdot (e_2 + 1)\)
• 이런식으로 소인수가 여러개일 때 위 식이 나온다는 걸 유추할 수 있습니다

 

 

약수의 합(Sum of divisors) 구하는 법

위에서와 동일하게 p=소수, e=소수가 나타난 횟수일 때 소인수가 1, 2, k개일 때를 생각해보겠습니다

• 소인수가 1개일 때, \(n=p_1^{e_1}\), 약수의 합은
  \[1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1}\]
• 소인수가 2개일 때, \(n=p_1^{e_1} \cdot p_2^{e_2}\), 위에서 만든 표와 동일하게 나타낼 수 있습니다. 다른 점이라면 이번에는 약수를 세는 것이 아니고 약수의 합을 구하는 것입니다. 약수의 합은 아래 식으로 나타낼 수 있습니다.
  \[\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right)\]\[= \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1}\]
• 소인수가 k개일 때, \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\), 아래 식을 구할 수 있습니다.
  \[\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1}\]

 

 

곱셈적 함수(Multiplicative function)

곱셈적 함수란 서로소 \(a\)와 \(b\)에 대해 함수 \(f(x)\)가 아래 성질을 만족할 때를 말합니다.

\[f(a \cdot b) = f(a) \cdot f(b)\]

\(d(n)\)과 \(\sigma(n)\) 둘 다 곱셈적 함수입니다. 곱셈적 함수라는 점을 이용해 정수론 문제를 유용하게 해결할 수 있다고 합니다.