$N$의 양의 약수의 합이 짝수일까? 홀수일까?

한 줄 요약: $N$이 제곱수이거나 제곱수를 $2$로 나눈 값이라면 양의 약수의 합은 홀수고 아니라면 짝수다.

($16(4^2)$, $72(\frac{{12}^2}{2})$, $\cdots$ 등은 홀수, $19$, $34$, $\cdots$ 등은 짝수)

 

$N$이 주어졌을 때 양의 약수의 합이 무엇이냐고 한다면, 직접 약수를 구해서 합을 더해 줄 수 있다. 그리고 그 값이 홀수인지 짝수인지 판단 해볼수 있다. 그렇다고 이 방식이 컴퓨터로 계산했을 때 ${10}^{18}$ 스케일 정도까지는 폴라드 로 알고리즘을 사용한다면 엄청 느리거나 하지 않는다. 하지만 우리는 $N$을 이렇게도 나타낼 수도 있다.

 

$N=p_1^{q_1}{p}_2^{q_2}\cdots p_n^{q_n}$ (단, $p_i$는 소수, $q_i\ge 1$)

 

예시로는 $120=2^3\times 3\times 5$가 있다. $N$의 양의 약수의 합을 $\sigma (N)$이라고 정의하면 다음과 같은 식이 나온다.

 

$\sigma (N)=(1+p_1+p_1^2+\cdots +p_1^{q_1})$ $\times$ $(1+p_2+p_2^2+\cdots +p_2^{q_2})$ $\times \cdots \times$ $(1+p_n+p_n^2+\cdots +p_n^{q_n})$

 

위의 예시를 들었던 $120$은, $\sigma (120)=(1+2+2^2+2^3)\times (1+3)\times (1+5)=15\times 4\times 6=360$가 되고 실제로 $120$의 약수 $1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120$을 모두 다 더하면 $360$이다.

 

자 그러면 대충 이론을 확인했으니 '어떤 값은 짝수고 어떤 값은 홀수일까?' 라는 주제로 다시 돌아가보자.

$K=$ $k_1\times k_2\times \cdots \times k_n$라는 식이 주어졌을 때 $k_i$가 하나라도 짝수라면 $K$는 무조건 짝수가 된다.

이를 다른 말로 하면 $k_i$가 전부 홀수여야 $K$가 홀수라는 의미이다.

 

$p_i$는 소수이므로 $2$를 제외한 모든 소수는 홀수이기 때문에 $p_i$가 짝수인지 홀수인지, 그리고 $q_i$가 짝수인지 홀수인지에 따라서 조건을 나눌 수 있다.

간편하게 $k_i=(1+p_i+p_i^2+\cdots +p_i^{q_i})$라고 정의한다.

 

1) $p_i$가 짝수인 경우

 

1-1) $q_i$가 짝수인 경우

$1$을 제외한 $p_i,p_i^2,\cdots ,p_i^{q_i}$은 모두 짝수이므로 $k_i$는 홀수다.

 

1-2) $q_i$가 홀수인 경우

$1$을 제외한 $p_i,p_i^2,\cdots ,p_i^{q_i}$은 모두 짝수이므로 $k_i$는 홀수다.

 

따라서 $p_i$가 짝수라면 $q_i$에 상관없이 $k_i$가 홀수다.

 

2) $p_i$가 홀수인 경우

 

2-1) $q_i$가 짝수인 경우

$1,p_i,p_i^2,\cdots ,p_i^{q_i}$은 모두 홀수이고, 홀수를 홀수 개($q_i$가 짝수이므로, $q_i+1$은 홀수)만큼 더하는 것이니 $k_i$는 홀수다.

 

2-2) $q_i$가 홀수인 경우

$1,p_i,p_i^2,\cdots ,p_i^{q_i}$은 모두 홀수이고, 홀수를 짝수 개($q_i$가 홀수이므로, $q_i+1$은 짝수)만큼 더하는 것이니 $k_i$는 짝수다.

 

따라서 $p_i$가 홀수라면 $q_i$가 짝수일 때 $k_i$가 홀수다.

 

그러면 $\sigma (N)=k_1\times k_2\times \cdots \times k_n$이 홀수가 되기 위해서는 $k_i$ 모두가 홀수여야 하므로 $p_i$에 $2$(짝수)가 있는 경우와 없는 경우로 나누자.

$p_i$에 짝수가 없는 경우는 $k_i$가 모두 홀수여야 한다. $q_i$는 모두 짝수이므로, $p_1^{2z_1}{p}_2^{2z_2}\cdots p_n^{2z_n}=(p_1^{z_1}{p}_2^{z_2}\cdots p_n^{z_n}{)}^2$로 나타낼 수 있다.

$p_i$에 짝수가 있는 경우는 $p_1=2$고 $q_1$이 짝수면 위의 내용과 똑같고 $q_1$이 홀수면 $p_1^{2z_1-1}\times p_2^{2z_2}\times \cdots \times p_n^{2z_n}=\frac{(p_1^{z_1}{p}_2^{z_2}\cdots p_n^{z_n}{)}^2}{2}$이다. 따라서 $N$이 제곱수이거나 제곱수를 $2$로 나눈 값이면 약수의 합이 홀수고 아니라면 짝수이다.

 

관련 문제

BOJ 11692