페르마 두 제곱수 정리

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

정의

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

• ${\displaystyle p=x^{2}+y^{2}}$인 정수 ${\displaystyle x,y}$가 존재한다.
• ${\displaystyle 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이기 때문이다. 반대 방향에 대한 몇 가지 증명은 아래와 같다.

오일러의 증명

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

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

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

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

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

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

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

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

${\displaystyle {\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle p>q>r>\cdots }$

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

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

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

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

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

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

이다. 따라서

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

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

이를 위해, 수열

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

의 1계 유한 차분

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

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

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

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

투에 보조정리를 통한 증명

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

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

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

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

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

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

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

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

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

이다.

“한 문장” 증명

유한 집합^[4]:144

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

위의 대합

${\displaystyle (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}$

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

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

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

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

를 만족시킨다.

일반화

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

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

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

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

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

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

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

증명

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

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

이므로, 어떤 정수 ${\displaystyle z}$에 대하여

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

가 성립한다. 따라서,

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

이므로,

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

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

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

와 동치이다.

반대로,

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

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

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

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

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

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

${\displaystyle (r,s)\neq (r',s')}$

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

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

${\displaystyle {\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}}}$

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

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

그렇다면,

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

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

이며,

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

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

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

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

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

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

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

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

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

역사

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

같이 보기

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