$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} \geq 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