소인수분해로 약수의 개수 총합 구하기 일반화

이번 시간에는 소인수분해와 표를 이용해 약수를 체계적으로 구하는 방법을 학습하고 약수의 개수를 구하는 과정을 일반화 하여 일반적 식으로 정리해 보기로 하자.

소인수분해와 약수, 약수의 개수

$12$를 소인수분해하여 나타내면 다음과 같다. $12=2^2\times3$
소인수분해를 이용해 약수와 약수의 개수를 어떻게 구할 수 있을까? 12의 약수는 12를 나누어 떨어지게 하는 수 이므로 다음과 같이 표현할 수 있다.

$\dfrac{12}{12\text{의 약수}}=\dfrac{{\color{blue}2^2}\times{\color{red}3^1}}{\text{12의 약수}}=\text{자연수}$

이를 통해 $12$의 약수는${\bbox[#ffff00]{2^{\square}}}\times{\bbox[#94feff]{3^{\triangle}}}$로 표현할 수 있음을 알 수 있다.

실제로 $12$의 약수는 $\{1,2,3,4,6,12\}$이고, 소인수분해 가능한 수를 소인수분해로 나타내면 $1,2,3,2^2,2\times3,2^2\times 3$임을 확인할 수 있다.

다음 두 자리 $\bbox[#ffff00]{2^{\square}}, \bbox[#94feff]{3^{\triangle}}$에 올 수 있는 수는 분자${\bbox[#ffff00]{2^2}}\times{\bbox[#94feff]{3^1}}$와 약분되는 수이고, 이는 두 자리에 다음과 같은 수들이 오는 경우에만 가능하다.

$\bbox[#ffff00]{2^{\square}}$자리: $\bbox[#ffff00]{2^2}\text{의 약수}\rightarrow1, 2^1, 2^2$
$\bbox[#94feff]{3^{\triangle}}$자리: $\bbox[#94feff]{3^1}\text{의 약수}\rightarrow 1,3^1$

따라서 12의 약수는 다음과 같다.

$\therefore \;12 \text{의 약수}:[\bbox[#ffff00]{2^2}\text{의 약수}]\times [\bbox[#94feff]{3^1}\text{의 약수}]$

두 자리에 올 수있는 수의 모든 경우를 고려하는 방법은 ‘표(2차원 분석도구)’를 이용하는 것이다. 표를 이용하여 가능한 조합을 모두 고려하면 다음과 같다.

이를 통해 다음 사실들을 알 수 있다.

소인수분해와 약수, 약수의 개수 구하기

위의 사실을 이용하여 소인수분해를 이용해 약수를 직접구하는 방법과 약수의 개수를 구하는 방법에 대해 정리해 보기로 하자.

소인수가 1개인 자연수

소인수분해한 결과 소인수가 1개인 자연수의 약수를 구하는 방법과 약수의 개수를 구하는 방법에 대해 정리해 보자.

• $2^{\bbox[#ffff00]{3}}$의 약수: $\bbox[#ffc5fd]{1},2,2^2,2^{\bbox[#ffff00]{3}}$
• $2^3$의 약수개수: $\bbox[#ffff00]{3}+\bbox[#ffc5fd]{1}$

약수는 1을 포함하기 때문에 지수의 개수($\bbox[#ffff00]{3}$) 보다 $\bbox[#ffc5fd]{1}$개 더 많다. 이를 문자로 정리하면 다음과 같다.

정리

자연수 $n$과 소수$p$에 대하여

• $p^n$의 약수의 개수: $n+1$

소인수가 2개인 자연수

소인수분해한 결과 소인수의 개수가 2개인 자연수의 약수를 구하는 방법과 약수의 개수를 구하는 방법을 $12=2^2\times3$을 이용해 정리해보자.

• $12=2^2\times3^1$의 약수는 표를 이용해 구할 수 있다.
  가로축: ${\color{blue}2^2\text{의 약수}}\rightarrow 1,2,2^2$
  세로축: ${\color{red}3^1\text{의 약수}}\rightarrow 1,3$
• $12$의 약수 개수는 표의 칸수와 같다.
  $\;\;=[ {\color{blue}2^{\bbox[#ffff00]{2}}\text{의 약수 개수}}]\times [{\color{red}3^{\bbox[#ffff00]{1}}\text{의 약수 개수}}]$
  $=({\color{blue}\bbox[#ffff00]{2}}+\bbox[#ffc5fd]{1})({\color{red}\bbox[#ffff00]{1}}+\bbox[#ffc5fd]{1})$

정리

자연수 $m,n$과 소수$p,q$에 대하여

• $p^m\times q^n$의 약수개수: $(m+1)(n+1)$

소인수가 3개 이상인 자연수

소인수분해한 결과 소인수의 개수가 3개일 때 어떻게 약수를 구하는 방법과 약수의 개수를 구하는 방법에 대해 알아 보기로 하자.

위의 개념을 응용하여 $60=\bbox[#ffff00]{2^2\times3^1}\times \bbox[#94feff]{5}$의 약수를 구하는 방법은 다음과 같다.

$60\text{의 약수}=[\bbox[#ffff00]{2^2\times3^1}\text{의 약수}]\times[\bbox[#94feff]{5}\text{의 약수}]$

• 가로축 : $\bbox[#ffff00]{2^2\times3^1}$의 약수
• 세로축 : $\bbox[#94feff]{5}$의 약수

위의 과정을 통해 $60$의 약수 개수는 $2^2\times3^1$의 약수의 개수와 $5$의 약수의 개수를 곱하면 된다는 사실을 알 수 있다. 이를 종합하면 다음과 같은 결과를 얻을 수 있다.

• $60=2^{\bbox[#ffff00]{2}}\times3^{\bbox[#94feff]{1}}\times5^{\bbox[#ffc5fd]{1}}$의 약수 개수
  $=(\bbox[#ffff00]{2}+1)(\bbox[#94feff]{1}+1)(\bbox[#ffc5fd]{1}+1)$

이 내용도 문자를 이용해 정리해 보면 다음과 같다.

정리

자연수 $l,m,n$과 소수$p,q,r$에 대하여

• $p^l\times q^m\times r^n$의 약수의 개수:
  $(l+1)(m+1)(n+1)$

약수의 개수와 총합 구하기 일반화(심화)

약수의 개수 구하기 일반화

자연수$N$의 소인수분해가 $N=p_1^{n_1}\times p_2^{n_2} \times \cdots p_k^{n_k}$일 때 $N$의 약수의 개수는 다음과 같다.
$(n_1+1) \times (n_2+1) \times\ \cdots \times (n_k+1)$

약수의 총합구하기

$12=2^2\times3$의 약수의 총합 $S$는 다음과 같이 구할 수 있다.

• $S=(1+2+2^2)(1+3)\;\because\;\text{분배 법칙}$

이를 문자를 이용해 정리하면 다음과 같다.

자연수$N$의 소인수 분해가 $N=p^m\times q^n\;(p,q:\text{ 소인수},\;m,n:\text{ 자연수})$일 때, $N$의 약수의 총합$S$는 다음과 같다.

• $S=\begin{Bmatrix}(1+p+p^2+\cdots+p^m)\\[1em]
  \times (1+q+q^2+\cdots+q^n)\\[1em]
  \end{Bmatrix}$

약수의 총합구하기 일반화

자연수$N$의 소인수분해가 $N=p_1^{n_1}\times p_2^{n_2} \times \cdots p_k^{n_k}$일 때 $N$의 약수의 총합 $S$는 다음과 같다.
$S=\begin{Bmatrix}(1+p_1+p_1^2+\cdots+p_1^{n_1})\\[1em]
\times (1+p_2+p_2^2+\cdots+p_2^{n_2})\\[1em]
\times \cdots\\[1em]
\times (1+p_k+p_k^2+\cdots+p_k^{n_k})\\[1em]
\end{Bmatrix}$