10. 자연수를 네 개 이하 제곱수의 합으로 나타내기 (下)

아직 上편을 본 적이 없다면, 일단 보고 오자.

 

Part II. 페르마의 두 제곱수 정리

이번에는 사원수 대신에 복소수를 가져와 보자. 사원수 때와 유사하게, 복소수 \(z=x+iy\)의 norm은 \(\text{N}(z)=z\overline z=x^2+y^2\)로 정의된다. 또한 \(\text{N}(zw)=\text{N}(z)\text{N}(w)\) 역시 사원수 때와 마찬가지로 성립하므로, 어떤 자연수를 두 제곱수로 나타낼 수 있음의 필요조건은 그 자연수의 모든 소인수가 두 제곱수의 합으로 표현될 수 있음이다.

모든 소수가 두 제곱수의 합으로 표현될 수는 없다. 당장 \(3\)만 해도 두 제곱수의 합으로 표현될 수 없는 소수이다. 임의의 제곱수는 \(4\)로 나눈 나머지가 \(0, 1\)이므로, 두 제곱수의 합은 \(4\)로 나눈 나머지가 \(0, 1, 2\)가 된다. 따라서, \(p=4n+3\)꼴의 홀수 소수는 절대 두 제곱수의 합으로 나타낼 수 없다.

그러면 그렇지 않은 모든 소수는 두 제곱수의 합으로 표현할 수 있을까? 일단 \(2=1^2+1^2\)이니, 고려해야 할 대상은 \(p=4n+1\)꼴의 홀수 소수 뿐이다. 답부터 미리 말하자면, 이러한 소수가 모두 두 제곱수의 합으로 표현이 가능하다는 것이 페르마의 두 제곱수 정리이다.

 

오래 연구된 만큼 증명 방법은 여러 가지가 있다. 무한 강하법을 이용하는 길고 복잡한 오일러의 증명이 있고, 이차 형식을 이용한 라그랑주의 증명법과, 복소수판 립시츠 정수인 가우스 정수를 이용한 데데킨트의 방법.

그리고 히스-브라운이 제시한 involution을 이용한 놀랄 만큼 간단한 증명과, 이를 더욱 간단하게 만든 재기어의 한 문장 짜리 증명 또한 있다.

다만 이 포스트에서 다룰 것은 투에의 보조정리를 사용한 증명이다.

 

우선 투에 보조정리부터 증명을 하고 넘어가도록 하자. 이 정리의 증명은 기초적인 정수론과 비둘기집의 원리를 이용한다.

두 정수 \(n, a\)가, \(n>0, (a,n)=1\)을 만족시킨다고 하자. 그러면 당연히 합동식 \(ax\equiv y\pmod{n}\)은 무수히 많은 정수해를 가진다. 이 때, \(x, y\)가 \(0\)과 충분히 가깝도록 만들 수 있는지 없는지에 대한 해답을 투에 보조정리가 제시한다.

집합 \(S=\{(x,y)\mid 0\le x,y\le \lfloor\sqrt{n}\rfloor\}\)는 원소의 갯수가 \((1+\lfloor\sqrt{n}\rfloor)^2\)인 유한집합이다. \(\lfloor x \rfloor > x-1\)이 성립하기 때문에, \(S\)의 원소 수는 \(n\)보다 많다.

그러므로 함수 \(f(x,y)=ax-y+n\mathbb{Z}\)로 정의된 \(f:S\to\mathbb{Z}_n\)은 단사가 될 수 없는 전사함수이다. 이 말은, \(f(x_1,y_1)=f(x_2,y_2)\)인 서로 다른 \(S\)의 원소 \((x_1,y_1), (x_2,y_2)\)가 존재한다는 뜻.

그러하다면, \(x=x_1-x_2, y=y_1-y_2\)로 둘 시 \(ax_1-y_1+n\mathbb{Z}=ax_2-y_2+n\mathbb{Z}\)가 성립하므로, \(ax-y\in n\mathbb{Z}\)가 된다. 이는 \(ax\equiv y\pmod{n}\)라는 말.

그리고, \((x_1,y_1), (x_2,y_2)\)가 서로 다른 \(S\)의 원소이므로 \(0<|x|,|y|\le \lfloor\sqrt{n}\rfloor\) 또한 성립한다. 곧, 합동식 \(ax\equiv y \pmod{n}\)의 해를 기껏해야 \(0\)과 \(\sqrt{n}\)만큼만 떨어지도록 만들 수 있다는 것이다.

 

소수 \(p=4n+1\)를 잡자. 그러면 윌슨 정리에 의해서 \(-1\equiv (p-1)! = (4n)!\pmod{p}\)이 성립한다. \((4n)!\equiv 1\cdot2\cdots 2n\cdot (-2n)\cdots(-2)\cdot(-1)\equiv(2n)!^2 \pmod{p}\)이 되기 때문에, \(a^2\equiv -1\pmod p\)인 \(a\)가 \(\pm (2n)!\)와 \(\bmod p\)로 합동이게 존재하게 된다.

당연히 \((p,a)=1\)이기 때문에, 투에 보조정리에 의해서 \(ax\equiv y\pmod p\)를 만족시키는 두 정수 \(x, y\)가 \(0<|x|,|y|<\sqrt{p}\)이게 존재한다.

이제 이 합동식의 양 변을 제곱하게 되면 \(-x^2\equiv a^2x^2\equiv y^2\pmod p\). 곧 \(x^2+y^2\pmod p\)가 성립하게 된다. 그런데, \(0<x^2+y^2<2p\)이었으므로, \(x^2+y^2=p\)일 수밖에 없다.

따라서 임의의 \(4n+1\)꼴 소수인 \(p\)는 두 제곱수의 합으로 나타낼 수 있는 것이다.

 

 

Part III. 두 제곱수의 합으로 나타낼 수 있는 자연수

페르마의 두 제곱수 정리에 의하면, 우선 \(4n+1\)꼴의 소수 곱으로 표현되는 모든 자연수는 두 제곱수의 합으로 표시될 수 있다. 그리고 이것에 적절한 제곱수를 곱한 형태 역시 두 제곱수의 합으로 표시될 수 있다.

방금 언급한 꼴의 자연수 \(N\)은, \(4n+3\)꼴의 소수 \(p\)로 나누어떨어진다면 짝수 번 나누어떨어진다는. 곧 소인수분해를 하였을 때 \(p\)의 지수가 짝수라는 성질을 가지고 있다. 그러면 역으로 이런 형태의 자연수는 항상 두 제곱수의 합으로 표시될까?

이어질 증명은 이 물음에 대한 답이 그렇다는 증거를 제시한다.

 

소수 \(p=4n+3\)에 대해서, \(p^{2l-1}\mid N\)이고 \(p^{2l}\nmid N\)인 자연수 \(N\)이 두 제곱수의 합으로 \(N=X^2+Y^2\)와 같이 쓰여진다고 하자. 이 때, \(X, Y\)를 서로소라고 보아도 된다. \(d=(X,Y), X=dx, Y=dy\)로 둘 시, \(\frac{N}{d^2}\) 역시 \(p\)의 지수가 홀수가 되고, \(\frac{N}{d^2}=x^2+y^2\)로 두 제곱수의 합으로 표시되기 때문이다.

만약 \(X\)이 \(p\)의 배수가 된다면, \(Y^2=N-X^2\equiv 0\pmod{p}\)이 되므로 \(Y\) 역시 \(p\)의 배수가 된다. 그러니 \((p,X)=1\)이 된다. 따라서 적당한 정수 \(m\)이, \(Xm\equiv Y\pmod{p}\)이 성립하게 존재한다.

\(0\equiv N = X^2+Y^2=X^2+X^2m^2=X^2(1+m^2)\pmod{p}\)이게 되고, 다시 \((p,X)=1\)이기 때문에 \(1+m^2\equiv0\pmod{p}\), 곧 \(m^2\equiv-1\pmod{p}\)이 된다.

이제 군론의 용어를 살짝 가져와 보자. \(\mathbb{Z}_p=F\)에 대해서, \(F^{\times}\)의 order는 \(4n+2\)이다. 따라서, 모든 \(F^{\times}\)의 원소는 order를 \(4n+2\)의 약수로 가진다. 그러나 \(m^4\equiv1\pmod{p}\)이고, \(m,m^2\not\equiv1\pmod{p}\)이 되기 때문에, \(m\in F^{\times}\)은 order가 \(4\)가 된다. 당연히 \(4\)는 \(4n+2\)의 약수가 아니다. 모순.

따라서 그러한 \(X,Y\)는 존재치 않는다. 곧 \(N\)은, \(4n+3\)꼴의 소수 \(p\)의 지수가 홀수인 자연수는 절대 두 제곱수의 합으로 나타낼 수가 없다.

 

 

Part IV. 르장드르의 세 제곱수 정리

어떤 제곱수든, \(4\)로 나눈 나머지는 \(0, 1\)이며, \(8\)로 나눈 나머지는 \(0,1,4\)뿐이다. 이를 이용하면 세 제곱수의 합으로 나타낼 수 없는 수들을 가려 낼 수 있다.

만약 자연수 \(N\)이 다음 식 \(N=a^2+b^2+c^2\)을 만족시킨다고 하자. \(N\)이 4의 배수라고 하면, \(a,b,c\)는 모두 짝수가 되어야만 한다. 곧, \(\frac{N}4=\left(\frac{a}{2}\right)^2+\left(\frac{b}{2}\right)^2+\left(\frac{c}{2}\right)^2\) 또한 세 제곱수의 합이다. 이의 대우를 취하면, \(N\)이 세 제곱수의 합으로 표현되지 않을 때 \(4N\)도, \(4^2N\)도, 계속 적용해 나가면 모든 \(4^nN\)이 세 제곱수의 합으로 표현되지 않는다.

위에서 \(8\)로 나눈 나머지를 이용하면, \(a^2+b^2+c^2\not\equiv7\pmod8\)임을 알 수 있다. 그러니 모든 \(8m-1\)꼴의 정수는 세 제곱수의 합으로 쓸 수 없고, 위에서 논의한 것을 그대로 대입하면 \(4^n(8m-1)\)꼴의 모든 정수는 세 제곱수의 합으로 나타낼 수가 없다.

이 역도 참이라는 것이 르장드르의 세 제곱수 정리가 된다. 정확하게는, 다음과 같은 명제가 말이다.

\[\forall\,0\le a,b,c\in\mathbb{Z},N\ne a^2+b^2+c^2\,\,\Leftrightarrow\,\,\exists n,m\in\mathbb{N}\,\text{s.t.}\,N=4^n(8m-1)\]

이것을 증명하는 것은 등차수열에서의 디리클레 정리나 민코프스키의 Convex Body Theorem, 르장드르 기호, 야코비 기호 등을 이용한 길고 지난한 길이 될 것이고, 한 개의 포스트로 정리하기 매우 힘들다. 다만 궁금한 이를 위하여 증명을 이 쪽에 남긴다.

 

 

Part I에서 모든 자연수는 기껏해야 네 개의 제곱수의 합으로 나타낼 수 있음을 보였다. Part III에서 두 제곱수의 합으로 나타내기 위한 조건을, Part IV에서 세 제곱수의 합으로 나타내기 위한 조건을 제시하였으며, 한 개의 제곱수의 합으로 나타내기 위한 조건은 워낙 당연하니.

지금껏 나온 조건들을 잘 종합해 보면 놀랍게도, 17633번 문제를 어렵지 않게 풀 수 있다!

아니라고? 일단 한 번 도전해 보자.