61. Sum of Squares

이번 글에서는 임의의 자연수 $p$를 최소 개수의 제곱수의 합으로 나타내는 문제를 살펴본다.

---

먼저 $p$를 제곱수 $1$개의 합으로 나타낼 수 있으려면 $x^2=p$를 만족하는 정수 $x$가 존재해야 한다는 사실은 쉽게 알 수 있다. $p$가 처음부터 제곱수였다면 $p$를 제곱수 $1$개의 합으로 나타낼 수 있다.

---

다음으로 $p$를 제곱수 $2$개의 합으로 나타낼 수 있는 경우를 알아본다. 먼저 임의의 제곱수를 $4$로 나눈 나머지를 구하면 다음과 같다:

• $(2k)^2=4k^2$
• $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$

그 밖의 경우가 존재하지 않으므로 제곱수를 $4$로 나눈 나머지는 $0$ 또는 $1$이고, 제곱수 $2$개를 더한 결과를 $4$로 나눈 나머지는 $0, 1, 2$가 될 수 있다. 따라서 $(4k+3)$ 꼴의 자연수를 제외한 나머지 자연수 중 어떤 수들이 제곱수 $2$개의 합으로 나타낼 수 있는지 확인한다.

 

먼저, $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$이므로 제곱수 $2$개의 합으로 나타낼 수 있는 자연수를 서로 곱하면 그 수 역시 제곱수 $2$개의 합으로 나타낼 수 있다. 또한 $d$에 $0$을 대입하면 $(a^2+b^2)c^2=(ac)^2+(bc)^2$이므로 제곱수 $2$개의 합으로 나타낼 수 있는 자연수에 제곱수를 곱해도 역시 제곱수 $2$개의 합으로 나타낼 수 있다.

 

또한, $a^2+b^2$이 $c^2+d^2$의 배수이고 $c^2+d^2$이 소수라고 하면, $d^2(a^2+b^2)-b^2(c^2+d^2)=(ad)^2-(bc)^2=(ad+bc)(ad-bc)$도 $c^2+d^2$의 배수이고 $ad+bc$ 또는 $ad-bc$중 최소한 하나는 $c^2+d^2$의 배수이다. $ad-bc$가 $c^2+d^2$의 배수라고 하면, 위에서 나온 식에 의해 $(ac+bd)^2$도 $c^2+d^2$의 배수이다. 또한 식의 양변을 $(c^2+d^2)^2$으로 나누면 $\frac{a^2+b^2}{c^2+d^2}=(\frac{ac+bd}{c^2+d^2})^2+(\frac{ad-bc}{c^2+d^2})^2$이고, 각각의 분수는 정수로 나타낼 수 있으므로 $\frac{a^2+b^2}{c^2+d^2}$은 제곱수 $2$개의 합으로 나타낼 수 있다. 따라서 제곱수 $2$개의 합으로 나타낼 수 있는 자연수를 제곱수 $2$개의 합으로 나타낼 수 있는 다른 자연수로 나누었을 경우 그 몫도 제곱수 $2$개의 합으로 나타낼 수 있으며, 이와 비슷하게 제곱수 $2$개의 합으로 나타낼 수 있은 자연수를 제곱수 $2$개의 합으로 나타낼 수 없는 자연수로 나누었을 경우 그 몫도 제곱수 $2$개의 합으로 나타낼 수 없다.

 

다음으로 $a$와 $b$가 서로소이고 $a^2+b^2$이 $2$보다 큰 자연수 $w$의 배수라고 하면, $xw, yw$가 $a, b$에 가장 가까운 값이 되게 하는 정수 $x, y$를 찾을 수 있다. 또한 $c=a-xw, d=b-yw$라고 하면 $|c|, |d| < \frac{w}{2}$이고, $a^2+b^2$을 $c, d, w, x, y$를 이용하여 나타내면 $(w$의 배수$)+c^2+d^2$ 꼴이 된다. $a^2+b^2$이 $w$의 배수이므로 $c^2+d^2$도 $w$의 배수이고, $\gcd(c, d)=g, c^2+d^2=wz$라고 하면 $\frac{wz}{g^2}=(\frac{c}{g})^2+(\frac{d}{g})^2 \le c^2+d^2 < (\frac{q}{2})^2+(\frac{q}{2})^2 = \frac{q^2}{2}$이다. 이때 $w$가 제곱수 $2$개의 합으로 나타낼 수 없는 수일 경우 $\frac{z}{g^2}$의 약수이면서 제곱수 $2$개의 합으로 나타낼 수 없는 자연수 $w'$이 존재하고, $w' < w$이고 $a^2+b^2$이 $w'$의 배수이므로 처음 과정으로 되돌아가면 $w'$보다 작은 자연수 $w'', w''', \ldots$가 계속해서 나오게 된다. 하지만 자연수 수열의 값이 무한히 작아지는 것은 불가능하므로 이는 모순이고, $w$는 제곱수 $2$개의 합으로 나타낼 수 있다. 따라서 $a$와 $b$가 서로소일 때 $a^2+b^2$의 약수는 모두 제곱수 $2$개의 합으로 나타낼 수 있다.

 

한편 $p$가 $(4k+1)$ 꼴의 소수일 경우 페르마의 소정리에 의해 $1 \le t \le 4k$를 만족하는 자연수 $t$에 대해 $t^{4k}$를$p$로 나눈 나머지는 항상 $1$이므로 $1 \le t < 4k$일 경우 $(t+1)^{4k}-t^{4k}$는 $p$의 배수이다. 또한 $(t+1)^{4k}-t^{4k}=\{(t+1)^{2k}+t^{2k}\}\{(t+1)^{2k}-t^{2k}\}$이므로 $(t+1)^{2k}+t^{2k}$ 또는 $(t+1)^{2k}-t^{2k}$이 $p$의 배수여야 한다. 이때 수열 $\{2^{2k}-1^{2k}, 3^{2k}-2^{2k}, \ldots \}$의 $(2k-1)$번째 계차항 수열이 $(2k)!$으로 $p$의 배수가 아니기 때문에 $(t+1)^{2k}-t^{2k}$은 $p$를 공약수로 갖지 않는다. 따라서 $(t+1)^{2k}+t^{2k}$가 $p$의 배수가 되게 하는 $t$가 하나 이상 존재한다. 이때 $(t+1)^{2k}+t^{2k}=\{(t+1)^k\}^2+(t^k)^2$이고 $(t+1)^k$와 $t^k$는 서로소이므로 $(t+1)^{2k}+t^{2k}$의 약수는 모두 제곱수 $2$개의 합으로 나타낼 수 있고, 이중 $p$가 한 번 이상 등장하므로 $p$는 제곱수 $2$개의 합으로 나타낼 수 있다.

 

이상을 종합하면, 소인수분해했을 때 $(4k+3)$ 꼴의 소인수의 지수가 모두 짝수인 자연수는 제곱수 $2$개의 합으로 나타낼 수 있다. 이를 페르마의 두 제곱수 정리(Fermat's Two-Square Theorem)라고 한다.

---

다음은 $p$를 제곱수 $3$개의 합으로 나타낼 수 있는 경우인데, 임의의 제곱수를 $8$로 나눈 나머지를 구하면 다음과 같다:

• $(4k)^2=16k^2$
• $(4k+1)^2=16k^2+8k+1=8k(2k+1)+1$
• $(4k+2)^2=16k^2+16k+4=16k(k+1)+4$
• $(4k+3)^2=16k^2+24k+9=8(k+1)(2k+1)+1$

그 밖의 경우가 존재하지 않으므로 제곱수를 $8$로 나눈 나머지는 $0, 1, 4$ 중 하나이며 제곱수 $3$개를 더한 결과를 $8$로 나눈 나머지는 $0, 1, 2, 3, 4, 5, 6$ 중 하나이다. 이로부터 $4^x(8k+7)$ 꼴의 자연수는 제곱수 $3$개의 합으로 나타낼 수 없음을 알 수 있다. 다른 모든 자연수는 항상 제곱수 $3$개의 합으로 나타낼 수 있는데, 이를 르장드르의 세 제곱수 정리(Legendre's Three-Square Theorem)라고 한다. 해당하는 증명은 생략한다.

---

$4^x(8k+7)$ 꼴이 아닌 모든 자연수를 제곱수 $3$개의 합으로 나타낼 수 있으므로, $4^x(8k+6)$ 꼴의 자연수를 제곱수 $3$개의 합으로 나타낸 다음 $4^x(=(2^x)^2)$을 더하면 제곱수 $3$개의 합으로 나타낼 수 없는 모든 자연수를 제곱수 $4$개의 합으로 나타낼 수 있다. 이 방법을 사용하지 않는 직접적인 증명이 존재하며, 이를 라그랑주의 네 제곱수 정리(Lagrange's Four-Square Theorem)라고 한다. (해당 증명은 추가할 예정이다)

---

위의 세 정리에 따르면 $p$를 소인수분해한 결과를 바탕으로 $p$를 제곱수의 합으로 나타낼 때 필요한 최소 개수의 제곱수를 알 수 있다. 그러한 제곱수를 찾는 방법은 여기서는 설명하지 않았으며 아래쪽의 참고 링크로 들어가면 설명을 볼 수 있다. 다만 $p$가 작을 경우 적절한 탐색으로 제곱수를 찾을 수 있다. $p$를 제곱수 $4$개의 합으로 나타내야 할 경우 한 제곱수를 $1$로 두면 $p-1$을 제곱수 $3$개의 합으로 나타내는 방법을 찾으면 된다. $p$를 제곱수 $3$개의 합으로 나타내야 할 경우 $p-x$가 $(4k+1)$ 꼴의 소수가 되게 하는 제곱수 $x$를 찾는 등의 방법이 존재한다. $p$를 제곱수 $2$개의 합으로 나타내야 할 경우, $(ax)^2+(bx)^2=cx^2$이고 $\gcd(a, b, c)=1$일 때 항상 $c-a$는 $(2k+1)^2$, $c-b$는 $2k^2$ 꼴이고 그런 $a$, $b$가 $c$값에 따라 유일하게 결정되므로 탐색의 범위를 줄일 수 있다. $(a, b$의 대소 관계는 알 수 없음$)$

 

[참고 링크]

 

제곱수를 찾는 방법

Fermat's Two-Square Theorem

Legendre's Three-Square Theorem

Lagrange's Four-Square Theorem

 

[연습문제]

 

BOJ 1699. 제곱수의 합 (Silver III)

위에서 설명한 방법대로 소인수분해를 해도 되고, 수가 작으므로 DP로 풀어도 된다.

 

BOJ 17633. 제곱수의 합 (More Huge) (Diamond IV)

입력의 범위가 $10^{18}$까지이므로 소인수분해가 강제된다. 다만 이전에 소개한 소인수분해를 쓸 수 없고 이후에 소개할 빠른 소인수분해 알고리즘을 이용해야 한다.