페르마의 두 제곱수 정리

이번 포스팅에서는 다음과 같은 정리를 증명해 보려고 한다.

Theorem 1. 페르마의 두 제곱수 정리
어떤 소수 $p$ ($p > 2$)가 두 제곱수의 합, 즉 자연수 $x, y$에 대해 $$p = x^2 + y^2$$으로 나타내어질 필요충분조건은 $p \equiv 1 \mod 4$ 인 것이다.

$\Rightarrow$ 거의 자명. 모든 제곱수는 모듈러 4에서 1 또는 0이고 (홀수를 제곱하면 1, 짝수를 제곱하면 0임이 어렵지 않다), 이를 더하여 $4k+3$ 형태의 홀수는 절대 얻을 수 없다. 따라서, 소수가 $4k + 1$ 인 것은 두 제곱수의 합이기 위한 필요조건임을 안다.

$\Leftarrow$ 긴 여행을 떠나야 한다 (...) Wikipedia나 http://www.secmem.org/blog/2019/10/18/sum-of-squares/ 같은 자료에는 Infinite Descent를 이용한 증명이 기술되어 있는데, 여기서는 Thue's Lemma와 Lagrange Theorem on groups 를 이용하는 증명을 적으려고 한다

먼저, 다음과 같은 Lemma를 보이자.

Lemma 2
어떤 소수 $p$에 대해, $p-1$이 모듈러 $p$ 에서의 Quadratic residue, 즉 $x^2 = p-1 \mod p$인 $x$가 존재할 필요충분조건은 $p$가 $4k+1$ 형태의 소수인 것이다.

Proof 순수하게 기초정수론의 지식만 써서도 증명이 충분히 가능하지만, 살짝 급발진해서 현대대수를 끼얹어서 오버킬을 시도하면 정말 쉬워진다.

$\Rightarrow$ 방향은, 군 $G$를 다음과 같이 정의하자. 군 $G = \Z / p\Z^*$ 는 $\Z_p$의 모든 Invertible element에 대하여, 이항연산으로 곱셈이 주어져 있는 군이다. 이러한 집합이 군을 이루는 것을 보이기는 어렵지 않다. 이제, 이 군의 Order는 정확히 $\phi(p)$ 이며, 이를 증명하기는 조금 더 귀찮지만 우리는 어차피 소수만 생각하고 있으므로, $\Z_p$에서 모든 nonzero element가 invertible함을 이용하면 $\abs{G} = p-1$은 자명하다.

이제, 만약 어떤 원소 $x$, $x^2 = -1 \mod p$ 가 존재한다면 $x$의 Order가 4여야 하고, $\Set{1, x, x^2, x^3}$ 이 $G = \Z / p\Z^*$의 Subgroup을 구성한다. Lagrange's Theorem 에 의하면, Finite group $G$와 그 Subgroup $H$에 대해, $H$의 Order는 $G$의 Order의 약수이다. 따라서 $4$가 $p-1$의 약수여야 한다.

$\Leftarrow$ 방향은, Finite Abelian Group에 대하여 Lagrange Theorem의 역이 참임을 이용해도 되고, Wilson's Theorem으로부터 직접 Construct해도 된다. 만약 직접 Construct 한다면, 다음의 수가 그냥 답이 된다.$$\left(\left(\frac{p-1}{2}\right)!\right)^2$$ Construct를 하지 않더라도, Order가 4인 subgroup of $G$가 존재한다는 사실로부터 거의 자명하다.

이제, 투에의 보조정리라고 알려진 다음 보조정리를 보이자.

Lemma 3 : Thue's Lemma

양의 정수 $n$과 $a$가 서로소일 때, $$0 < \abs{x}, \abs{y} \leq \sqrt{n}, \ \ ax \equiv y \mod n$$ 의 해 $x, y$가 존재한다.

Proof 증명은 먼저, $k = \lfloor{\sqrt{n}}\rfloor$라고 잡고 시작하자. 우리는 다음과 같은 집합을 생각한다. $$\Setcond{ax-y \mod n}{0 \leq x, y \leq k}$$ 이러한 집합의 원소의 개수가 $(k+1)^2$개로 $n$보다 조금 많으므로, 비둘기집의 원리에 의해 다음을 만족하는 $(u, v), (u', v')$ 가 존재한다. $$au-v = au'-v', \ \ (u, v) \neq (u', v')$$

이제 $x = u-u'$, $y = v-v'$라고 잡자. $k$ 보다 작거나 같은 수 두개를 뽑아 차를 구하는 중이므로, $x, y$의 절댓값이 $k$보다 작거나 같음은 자명하다. 이제, $x$, $y$ 중 하나라도 0이면, 합동식에 의해 다른 하나도 0이 되고, 그러면 $(u, v) \neq (u', v')$ 에 모순. 따라서 투에의 보조정리 증명이 끝났다.

준비가 끝났으니 보이려는 정리 (페르마의 두 제곱수 정리) 로 들어갈 수 있다.

소수 $p$에 대해, $p = 1 \mod 4$ 라고 하자. 이때 Lemma 2에 의하여 $x^2 = -1 \mod p $ 인 원소 $x$ 가 존재한다. 또한, Lemma 3에 의하여, (변수를 Renaming했지만) 다음과 같은 $u, v$가 존재한다. $$0 < \abs{u}, \abs{v} < \sqrt{p}, \ \ ux = v \mod p$$ 이 식은 다시, 양변을 제곱하고 우리가 제시한 $x$의 성질에 의해 $$u^2x^2 = v^2 = -u^2 \mod p$$ 이를 의미하게 된다. 이 식을 정리하면 $u^2 + v^2 \equiv 0 \mod p$ 가 된다. 마지막으로, 이렇게 찾은 $u^2 + v^2$에 대해, $0 < \abs{u}, \abs{v} < \sqrt{p}$에 의해, $0 < u^2, v^2 < p$ 가 성립한다. 따라서, $$u^2 + v^2 \equiv 0 \mod p, \Rightarrow p \leq u^2 + v^2 \text{ and } p | (u^2 + v^2)$$ $$u^2 + v^2 < 2p$$ 이 두 식을 결합하면, $u^2 + v^2 = p$ 가 보여졌다.