페르마 두 제곱수 정리

수론에서 페르마 두 제곱수 정리(-數定理, 영어: Fermat's theorem on sums of two squares)는 홀수 소수가 두 개의 제곱수의 합일 필요 충분 조건이 4에 대한 나머지가 1이라는 것이라는 정리이다.

정의

홀수 소수 $p$가 주어졌다고 하자. 페르마 두 제곱수 정리에 따르면, 다음 두 조건이 서로 동치이다.

• $p=x^{2}+y^{2}$인 정수 $x,y$가 존재한다.
• $p\equiv 1{\pmod {4}}$

사실, 4에 대한 나머지가 1인 소수는 무한히 많이 존재하며, 이에 대한 두 제곱수로의 표현은 (더하는 순서를 무시하면) 유일하다. 작은 소수의 경우는 다음과 같다.

p	min{x,y}	max{x,y}
2	1	1
5	1	2
13	2	3
17	1	4
29	2	5
37	1	6
41	4	5
53	2	7
61	5	6
73	3	8
89	5	8
97	4	9
…	…	…
(OEIS의 수열 A002331)	(OEIS의 수열 A002313)	(OEIS의 수열 A002330)

증명

전자가 후자를 함의하는 것은 자명하다. 이는 제곱수의 4에 대한 나머지는 0이거나 1이므로, 두 제곱수의 합의 4에 대한 나머지는 0, 1, 2이기 때문이다. 반대 방향에 대한 몇 가지 증명은 아래와 같다.

오일러의 증명

처음 출판된 증명은 레온하르트 오일러가 제시하였다. 이 증명은 무한 강하법을 사용하며, 이후에 제시된 증명들에 비하면 복잡하다. 이는 대략 다음과 같다.

우선, 다음과 같은 명제를 증명하자.

• 어떤 두 제곱수의 합인 수 $a^{2}+b^{2}$가 두 제곱수의 합인 소인수 $c^{2}+d^{2}$를 갖는다면, 몫 $(a^{2}+b^{2})/(c^{2}+d^{2})$은 두 제곱수의 합이다.

가정에 의하여, 다음이 성립한다.

$c^{2}+d^{2}\mid c^{2}(a^{2}+b^{2})-a^{2}(c^{2}+d^{2})=(bc+ad)(bc-ad)$

즉, $c^{2}+d^{2}\mid bc+ad$이거나, $c^{2}+d^{2}\mid bc-ad$이다. 편의상 전자를 가정하자. 그렇다면, 브라마굽타-피보나치 항등식

$(a^{2}+b^{2})(c^{2}+d^{2})=(bc+ad)^{2}+(bd-ac)^{2}$

에 의하여, $c^{2}+d^{2}\mid bc+ad$이므로, 두 수의 몫은 다음과 같이 두 제곱수의 합이다.

${\frac {a^{2}+b^{2}}{c^{2}+d^{2}}}=\left({\frac {bc+ad}{c^{2}+d^{2}}}\right)^{2}+\left({\frac {bd-ac}{c^{2}+d^{2}}}\right)^{2}$

이제, 다음과 같은 명제를 증명하자.

• 어떤 두 제곱수의 합인 수 $n$가 두 제곱수의 합이 아닌 약수 $p$를 갖는다면, 몫 $n/p$는 두 제곱수의 합이 아닌 약수를 갖는다.

귀류법을 사용하여, $n/p$의 모든 약수가 두 제곱수의 합이라고 하자. 그렇다면, 특히 $n/p$의 한 소인수 $q$는 두 제곱수의 합이며, 이전의 명제에 따라, $n/q$는 두 제곱수의 합이다. 이를 $n/p$의 (중복도를 감안한) 모든 소인수에 대하여 반복하면, $p$가 두 제곱수의 합이라는 결론을 얻으며, 이는 모순이다.

이제, 다음과 같은 명제를 증명하자.

• 정수 $a,b,p$가 $\gcd\{a,b\}=1$이고, $p\mid a^{2}+b^{2}$이라고 하자. 그렇다면, $\gcd\{c,d\}=1$이고, $p\mid c^{2}+d^{2}$이며, $c^{2}+d^{2}\leq p^{2}/2$인 정수 $c,d$가 존재한다.

다음과 같은 정수 $c,d$을 취하자.

$a\equiv c,\;b\equiv d{\pmod {p}}$

$|c|,|d|\leq {\frac {p}{2}}$

그렇다면, $\gcd\{a,b\}=1$이므로 $c^{2}+d^{2}\neq 0$이고, 또한

$c^{2}+d^{2}\equiv a^{2}+b^{2}\equiv 0{\pmod {p}}$

이다. $g,c',d'$을 다음과 같이 정의하자.

$g=\gcd\{c,d\},\;c'={\frac {c}{g}},\;d'={\frac {d}{g}}$

그렇다면, $\gcd\{c',d'\}=1$이다. 또한, $\gcd\{a,b\}=1$이므로, $\gcd\{g,p\}=1$이며, $g^{2}\mid (c^{2}+d^{2})/p$이다. 따라서, 다음이 성립한다.

$p\mid {\frac {c^{2}+d^{2}}{g^{2}p}}\cdot p={c'}^{2}+{d'}^{2}$

${c'}^{2}+{d'}^{2}\leq c^{2}+d^{2}\leq 2\cdot \left({\frac {p}{2}}\right)^{2}={\frac {p^{2}}{2}}$

즉, $c',d'$는 명제의 조건을 만족시킨다.

이제, 다음과 같은 명제를 증명하자.

• 정수 $a,b$가 $\gcd\{a,b\}=1$이라면, $a^{2}+b^{2}$의 모든 약수는 두 제곱수의 합이다.

귀류법을 사용하여, $p\mid a^{2}+b^{2}$가 두 제곱수의 합이 아니라고 가정하자. 이전의 명제에 따라, 다음을 만족시키는 정수 $c,d$를 취하자.

$\gcd\{c,d\}=1,\;p\mid c^{2}+d^{2},\;c^{2}+d^{2}\leq {\frac {p^{2}}{2}}$

그렇다면, $(c^{2}+d^{2})/p$는 두 제곱수의 합이 아닌 약수 $q\mid (c^{2}+d^{2})/p$를 갖는다. 또한 $q\leq p/2$이다. 이를 $q$와 $c^{2}+d^{2}$에 대하여 반복할 수 있다. 즉, 다음을 만족시키는 정수 $e,f$를 취하자.

$\gcd\{e,f\}=1,\;q\mid e^{2}+f^{2},\;e^{2}+f^{2}\leq {\frac {q^{2}}{2}}$

그렇다면, $(e^{2}+f^{2})/q$는 두 제곱수의 합이 아닌 약수 $r\mid (e^{2}+f^{2})/q$를 가지며, $r\leq q/2$이다. 이와 같이 반복하면, 양의 정수의 순감소 무한 수열

$p>q>r>\cdots$

를 얻으며, 이는 모순이다.

이제, 두 제곱수 정리를 증명하자. 소수 $p$가 어떤 정수 $n$에 대하여 $p=4n+1$라고 하자. 다음과 같은 정수 $a,b$가 존재한다고 가정하자.

$\gcd\{a,b\}=1$

$p\nmid a,b,a^{2n}-b^{2n}$

그렇다면, 페르마 소정리에 따라,

$p\mid a^{4n}-b^{4n}$

이다. 따라서

$p\mid a^{2n}+b^{2n}$

이며, 이전의 명제에 따라 $p$는 두 제곱수의 합이다. 즉, 두 제곱수 정리를 증명하려면 위와 같은 $a,b$를 찾으면 된다.

이를 위해, 수열

$(1^{2n},2^{2n},\dots ,(2n+1)^{2n})$

의 1계 유한 차분

$(2^{2n}-1^{2n},3^{2n}-2^{2n},\dots ,(2n+1)^{2n}-(2n)^{2n})$

을 생각하자. 귀류법을 사용하여, 1계 유한 차분의 모든 항이 $p$를 약수로 가진다고 가정하자. 그렇다면, 2계 유한 차분의 모든 항 역시 $p$를 약수로 가지며, 마찬가지로 3계, 4계, …, $2n$계 유한 차분의 모든 항 역시 $p$를 약수로 가진다. 그러나 수열 $1^{2n},2^{2n},\dots ,(2n+1)^{2n}$의 $2n$계 유한 차분은 모든 항이 $(2n)!$이며, $p$는 $(2n)!$의 약수가 아니다. 이는 모순이므로, 어떤 $b\in \{1,\dots ,2n\}$에 대하여

$p\nmid (b+1)^{2n}-b^{2n}$

이 성립한다. 즉, $b$와 $a=b+1$은 위와 같은 조건을 만족시킨다.

투에 보조정리를 통한 증명

만약 $p\equiv 1{\pmod {4}}$라고 하자.^:167-168 그렇다면, −1은 $p$에 대한 제곱 잉여이므로,

$a^{2}\equiv -1{\pmod {p}}$

인 정수 $a$가 존재한다. 또한 $\gcd\{p,a\}=1$이므로, 투에 보조정리에 따라,

$ax\equiv y{\pmod {p}}$

$0<|x|,|y|<{\sqrt {p}}$

를 만족시키는 정수 $x,y$가 존재한다. 따라서,

$y^{2}\equiv (ax)^{2}\equiv -x^{2}{\pmod {p}}$

이며, $p\mid x^{2}+y^{2}$이다. 또한, $0<x^{2}+y^{2}<2p$이므로,

$x^{2}+y^{2}=p$

이다.

한 문장 증명

유한 집합^:144

$S=\{(x,y,z)\in \mathbb {N} ^{3}\colon p=x^{2}+4yz\}$

위의 대합

$(x,y,z)\mapsto {\begin{cases}(x+2z,z,y-x-z)&x<y-z\\(2y-x,y,x-y+z)&y-z<x<2y\\(x-2y,x-y+z,y)&x>2y\end{cases}}\qquad \forall (x,y,z)\in S$

는 유일한 고정점 $(1,1,(p-1)/4)$를 가지므로, $|S|$는 홀수이다. 따라서 또 하나의 대합

$(x,y,z)\mapsto (x,z,y)\qquad \forall (x,y,z)\in S$

역시 적어도 하나의 고정점 $(x,y,y)$을 가지며, 이는

$x^{2}+(2y)^{2}=p$

를 만족시킨다.

일반화

$n=x^{2}+y^{2}$

임의의 양의 정수 $n$에 대하여, 다음 두 조건이 서로 동치이다.

• $n=x^{2}+y^{2}$인 정수 $x,y$가 존재한다.
• $n$은 4에 대한 나머지가 3인 홀수 중복도의 소인수를 가지지 않는다.

충분 조건은 어떤 두 제곱수의 합으로 표현되는 수의 곱도 두 제곱수의 합임을 이용하면 자명하다. 필요 조건의 증명에는 제곱 잉여의 이론을 이용하면 쉽게 증명할 수 있다.

$p=x^{2}+2y^{2}$

홀수 소수 $p$에 대하여, 다음 두 조건 역시 서로 동치이다.

• $p=x^{2}+2y^{2}$인 정수 $x,y$가 존재한다.
• $p\equiv 1,3{\pmod {8}}$

증명

우선, $p=x^{2}+2y^{2}$인 정수 $x,y$가 존재한다고 가정하자.^:321–322 그렇다면,

$\gcd\{p,x\}=\gcd\{p,y\}=1$

이므로, 어떤 정수 $z$에 대하여

$yz\equiv x{\pmod {p}}$

가 성립한다. 따라서,

$0\equiv x^{2}+2y^{2}\equiv y^{2}(z^{2}+2){\pmod {p}}$

이므로,

$z^{2}\equiv -2{\pmod {p}}$

이다. 즉, −2는 $p$에 대한 제곱 잉여이며, 이는

$p\equiv 1,3{\pmod {8}}$

와 동치이다.

반대로,

$p\equiv 1,3{\pmod {8}}$

라고 가정하자. 이는 −2가 $p$에 대한 제곱 잉여인 것과 동치이므로, 어떤 정수 $z$에 대하여

$z^{2}\equiv -2{\pmod {p}}$

가 성립한다. 다음과 같은 집합을 생각하자.

$\{\phi _{p}(rz+s)\colon r,s\in \{0,1,\dots ,\lfloor {\sqrt {p}}\rfloor \}\}\subseteq \mathbb {Z} /(p)$

여기서 $\phi _{p}(-)$는 $p$에 대한 나머지를 구하는 함수이다. 이 집합의 원소는 많아야 $p$개여야 하므로, 다음을 만족시키는 $r,r',s,s'\in \{0,1,\dots ,\lfloor {\sqrt {p}}\rfloor \}$가 존재한다.

$(r,s)\neq (r',s')$

$rz+s\equiv r'z+s'{\pmod {p}}$

사실, 다음과 같은 동치 관계에 따라, $r\neq r'$이며 $s\neq s'$이다.

${\begin{aligned}r=r'&\iff r-r'\equiv 0{\pmod {p}}\\&\iff (r-r')z\equiv 0{\pmod {p}}\\&\iff s-s'\equiv 0{\pmod {p}}\\&\iff s=s'\end{aligned}}$

이제, 정수 $x,y$를 다음과 같이 정의하자.

$x=|s-s'|,\;y=|r-r'|$

그렇다면,

$yz\equiv \pm x{\pmod {p}}$

$0<x,y<{\sqrt {p}}$

이며,

$0\equiv y^{2}(z^{2}+2)\equiv x^{2}+2y^{2}{\pmod {p}}$

이다. 즉, 다음을 만족시키는 정수 $m$이 존재한다.

$mp=x^{2}+2y^{2}$

또한, $0<x^{2}+2y^{2}<3p$이므로, $m\in \{1,2\}$이다. 만약 $m=1$이라면, $p$는 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다. 만약 $m=2$이라면, $2\mid x$이며,

$p=y^{2}+2\left({\frac {x}{2}}\right)^{2}$

이므로, 역시 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다.

$n=x^{2}+2y^{2}$

양의 정수 $n$에 대하여, 다음 두 조건이 서로 동치이다.

• $n=x^{2}+2y^{2}$인 정수 $x,y$가 존재한다.
• $n$은 8에 대한 나머지가 5, 7인 홀수 중복도의 소인수를 가지지 않는다.

역사

프랑스의 알베르 지라르가 1632년 처음 착상하고 역시 프랑스 수학자인 피에르 드 페르마가 1640년 마랭 메르센에게 보내는 편지에서 처음 증명을 제시하였으나 완전하지 못했다. 이 정리가 처음 증명된 것은 1749년 스위스 수학자 레온하르트 오일러가 크리스티안 골트바흐에게 보내는 편지에서였다.

같이 보기

• 투에 보조정리
• 라그랑주 네 제곱수 정리

외부 링크

• Weisstein, Eric Wolfgang. “Fermat's 4n+1 theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.