페르마 두 제곱수 정리

수론에서, **페르마 두 제곱수 정리**(-數定理, Fermat’s theorem on sums of two squares)는 홀수 소수가 두 정수의 제곱의 합일 필요충분조건이 4로 나눈 나머지가 1이라는 것이라는 정리이다.
# 정의
소수 p가 주어졌다고 하자. **페르마 두 제곱수 정리**에 따르면, 다음 두 조건이 서로 동치이다. * p=x^2+y^2인 정수 x,y가 존재한다. * p=2이거나 p\equiv 1\pmod 4 첫 번째 조건은 자명하게 두 번째 조건을 함의한다. 이는 제곱수의 4에 대한 나머지는 0이거나 1이기 때문이다. 반대 방향에서 p=2인 경우는 2=1^2+1^2이므로 자명하다. 남은 부분의 경우, 대표적인 증명들은 다음과 같다. 167-168 p가 소수이며, p\equiv 1\pmod 4라고 하자. 그렇다면, −1은 p에 대한 제곱 잉여이므로 :a^2\equiv-1\pmod p 인 정수 a가 존재하며, 또한 반드시 \gcd\\{p,a\\}=1이다. 투에 보조정리에 따라, :ax\equiv y\pmod p :01 인 가우스 정수 a,b\in\mathbb Z[i]가 존재한다. 여기서 \operatorname N은 가우스 정수의 체 노름이다. 그렇다면 :p^2=\operatorname N(p)=\operatorname N(a)\operatorname N(b) 이므로, :p=\operatorname N(a)=(\operatorname{Re}a)^2+(\operatorname{Im}a)^2 이다. 증명 끝 jstor=2323918 유한 집합 :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;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에 대하여, 다음 두 조건이 서로 동치이다. * n=x^2+y^2인 정수 x,y가 존재한다. * 4에 대한 나머지가 3인 n의 모든 소인수의 지수는 짝수이다. 증명 브라마굽타-피보나치 항등식 :(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2 에 따라, 두 제곱수의 합인 두 정수의 곱은 두 제곱수의 합이다. 특히, 두 제곱수의 합인 정수와 어떤 제곱수의 곱은 두 제곱수의 합이다. 페르마 두 제곱수 정리에 따라, 두 번째 조건은 충분하다. 두 번째 조건이 필요조건임은 다음과 같이 보일 수 있다. n=x^2+y^2이며, n=k^2m이며, m이 제곱 인수가 없는 정수라고 하자. 그렇다면 m의 임의의 소인수 p에 대하여 p\equiv1\pmod4임을 보이면 족하다. d=\gcd\\{x,y\\}라고 하자. 그렇다면 d^2\mid n이며, 따라서 d\mid k이다. 또한, :(k/d)^2m=(x/d)^2+(y/d)^2 :\gcd\\{x/d,y/d\\}=\gcd\\{p,x/d\\}=\gcd\\{p,y/d\\}=1 이다. 따라서 −1은 법 p에 대한 제곱 잉여이다. 즉, p\equiv1\pmod4이다. 증명 끝 임의의 양의 정수 n에 대하여, r_2(n)이 n을 두 정수의 제곱의 합으로 나타내는 방법의 가짓수라고 하자. 그렇다면 이는 다음과 같다. :r_2(n)=4\sum_{d\mid n}\chi(d) 여기서 :\chi(d)=\begin{cases} 0 & 2\mid d \\\ 1 & d\equiv1\pmod4 \\\ -1 & d\equiv3\pmod4 \end{cases} 는 법 4에 대한 유일한 비자명 디리클레 지표이다. 즉, r_2(n)은 n의 4로 나눈 나머지가 1인 양의 약수의 수와 4로 나눈 나머지가 3인 양의 약수의 수의 차의 4배이다. 특히, 임의의 정수의 4로 나눈 나머지가 1인 약수는 4로 나눈 나머지가 3인 약수보다 적지 않다.
## 가우스 정수의 경우
가우스 정수 a+bi\in\mathbb Z[i]에 대하여 (a,b\in\mathbb Z), 다음 두 조건이 서로 동치이다.jfm=66.0118.01410, §3, Theorem 2 * a+bi는 두 가우스 정수의 제곱의 합이다. * b는 짝수이며, a\not\equiv2\pmod4이거나 b\not\equiv2\pmod4이다. 보다 일반적으로, d\not\equiv1\pmod4인 허수 이차 수체 \mathbb Q(\sqrt d) 및 그 대수적 정수 a+b\sqrt d\in\mathcal O_{\mathbb Q(\sqrt d)}에 대하여 (a,b\in\mathbb Z), 다음 두 조건이 서로 동치이다.410–411, §4, Theorem 3 * a+b\sqrt d는 \mathcal O_{\mathbb Q(\sqrt d)}의 두 원소의 제곱의 합이다. * b는 짝수이며, dt^2-at+(b/2)^2가 양의 제곱수이며 \gcd\\{t,b/2,a-dt\\}가 두 제곱수의 합인 정수 t\in\mathbb Z가 존재한다.
# 표
소수를 두 정수의 제곱의 합으로 나타내는 방법 더하는 순서와 부호의 차이를 무시하면 유일하다. 작은 소수의 경우는 다음과 같다. (OEIS의 수열 A002331, A002313, A002330) :2=1^2+1^2 :5=1^2+2^2 :13=2^2+3^2 :17=1^2+4^2 :29=2^2+5^2 :37=1^2+6^2 :41=4^2+5^2 :53=2^2+7^2 :61=5^2+6^2 :73=3^2+8^2 :89=5^2+8^2 :97=4^2+9^2
# 관련 정리

## x2+2y2
소수 p에 대하여, 다음 두 조건 역시 서로 동치이다. * p=x^2+2y^2인 정수 x,y가 존재한다. * p=2이거나 p\equiv 1,3\pmod 8 321–322 우선, p=x^2+2y^2인 정수 x,y가 존재한다고 가정하자. 그렇다면, :\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)\ne(r',s') :rz+s\equiv r'z+s'\pmod p 사실, 다음과 같은 동치 관계에 따라, r\ne r'이며 s\ne s'이다. :\begin{align}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{align} 이제, 정수 x,y를 다음과 같이 정의하자. :x=|s-s'|,\;y=|r-r'| 그렇다면, :yz\equiv\pm x\pmod p :0 이며, :0\equiv y^2(z^2+2)\equiv x^2+2y^2\pmod p 이다. 즉, 다음을 만족시키는 정수 m이 존재한다. :mp=x^2+2y^2 또한, 0이므로, m\in\\{1,2\\}이다. 만약 m=1이라면, p는 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다. 만약 m=2이라면, 2\mid x이며, :p=y^2+2\left(\frac x2\right)^2 이므로, 역시 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다. 증명 끝 보다 일반적으로, 양의 정수 n에 대하여, 다음 두 조건이 서로 동치이다. * n=x^2+2y^2인 정수 x,y가 존재한다. * n의 8로 나눈 나머지가 5나 7인 모든 소인수의 지수는 짝수이다.
## x2+3y2
소수 p에 대하여, 다음 두 조건이 서로 동치이다. * p=x^2+3y^2인 정수 x,y가 존재한다. * p=3이거나 p\equiv1\pmod3 보다 일반적으로, 양의 정수 n에 대하여, 다음 두 조건이 서로 동치이다. * n=x^2+3y^2인 정수 x,y가 존재한다. * n의 3으로 나눈 나머지가 2인 모든 소인수의 지수는 짝수이다. 양의 정수 n을 x^2+3y^2의 꼴로 나타내는 방법의 가짓수는 다음과 같다. :r_{x^2+3y^2}(n)=\begin{cases} 0 & 2\nmid e(2,n) \\\ 12\sum_{d\mid n/2^{e(2,n)\chi(d) & e(2,n)=0 \\\ 36\sum_{d\mid n/2^{e(2,n)\chi(d) & 2\mid e(2,n)\land e(2,n)>0 \end{cases} 여기서 * e(2,n)은 2의 n에서의 소인수 지수이다. * \chi는 법 3에 대한 유일한 비자명 디리클레 지표이다. \chi(d)=\begin{cases}0 & 3\mid d \\\ 1 & d\equiv1\pmod3 \\\ -1 & d\equiv2\pmod3 \end{cases}
# 역사
프랑스의 알베르 지라르가 1632년 처음 착상하고 역시 프랑스 수학자인 피에르 드 페르마가 1640년 마랭 메르센에게 보내는 편지에서 처음 증명을 제시하였으나 완전하지 못했다. 이 정리가 처음 증명된 것은 1749년 스위스 수학자 레온하르트 오일러가 크리스티안 골트바흐에게 보내는 편지에서였다. 오일러의 증명은 무한 강하법을 사용하며, 이후에 제시된 증명들에 비하면 복잡하다. 이는 대략 다음과 같다.쪽=3–40쪽=3–13 제목=오일러의 증명 우선, 다음과 같은 명제를 증명하자. * 어떤 두 제곱수의 합인 수 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\le p^2/2인 정수 c,d가 존재한다. 다음과 같은 정수 c,d을 취하자. :a\equiv c,\;b\equiv d\pmod p :|c|,|d|\le\frac p2 그렇다면, \gcd\\{a,b\\}=1이므로 c^2+d^2\ne 0이고, 또한 :c^2+d^2\equiv a^2+b^2\equiv 0\pmod p 이다. g,c',d'을 다음과 같이 정의하자. :g=\gcd\\{c,d\\},\;c'=\frac cg,\;d'=\frac dg 그렇다면, \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^2p}\cdot p={c'}^2+{d'}^2 :{c'}^2+{d'}^2\le c^2+d^2\le 2\cdot\left(\frac p2\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\le\frac{p^2}2 그렇다면, (c^2+d^2)/p는 두 제곱수의 합이 아닌 약수 q\mid(c^2+d^2)/p를 갖는다. 또한 q\le p/2이다. 이를 q와 c^2+d^2에 대하여 반복할 수 있다. 즉, 다음을 만족시키는 정수 e,f를 취하자. :\gcd\\{e,f\\}=1,\;q\mid e^2+f^2,\;e^2+f^2\le\frac{q^2}2 그렇다면, (e^2+f^2)/q는 두 제곱수의 합이 아닌 약수 r\mid(e^2+f^2)/q를 가지며, r\le 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은 위와 같은 조건을 만족시킨다. 증명 끝