페르마 두 제곱수 정리

수론에서, **페르마 두 제곱수 정리**(-數定理, )는 홀수 소수가 두 정수의 제곱의 합일 필요충분조건이 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이므로 자명하다. 남은 부분의 경우, 대표적인 증명들은 다음과 같다.

p가 소수이며, p\equiv 1\pmod 4라고 하자. 그렇다면, −1은 p에 대한 제곱 잉여이므로
:a^2\equiv-1\pmod p
인 정수 a가 존재하며, 또한 반드시 \gcd\{p,a\}=1이다. 투에 보조정리에 따라,
:ax\equiv y\pmod p
:0
를 만족시키는 정수 x,y가 존재한다. 따라서
:x^2+y^2\equiv x^2+a^2x^2\equiv0\pmod p
:0
이다. 즉, x^2+y^2=p이다.

p가 소수이며, p\equiv 1\pmod 4라고 하자. 그렇다면, p는 가우스 소수가 아니며, 따라서
:p=ab
:\operatorname N(a),\operatorname N(b)>1
인 가우스 정수 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
이다.

유한 집합
: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)&x2y
\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), 다음 두 조건이 서로 동치이다.
* 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), 다음 두 조건이 서로 동치이다.
* 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의 수열 , , )
: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

## 관련 정리
### x<sup>2</sup>+2y<sup>2</sup>
소수 p에 대하여, 다음 두 조건 역시 서로 동치이다.
* p=x^2+2y^2인 정수 x,y가 존재한다.
* p=2이거나 p\equiv 1,3\pmod 8

우선, 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인 모든 소인수의 지수는 짝수이다.

### x<sup>2</sup>+3y<sup>2</sup>
소수 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년 스위스 수학자 레온하르트 오일러가 크리스티안 골트바흐에게 보내는 편지에서였다. 오일러의 증명은 무한 강하법을 사용하며, 이후에 제시된 증명들에 비하면 복잡하다. 이는 대략 다음과 같다.

우선, 다음과 같은 명제를 증명하자.
* 어떤 두 제곱수의 합인 수 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은 위와 같은 조건을 만족시킨다.

## 같이 보기
* 투에 보조정리
* 라그랑주 네 제곱수 정리

## 참고 문헌

## 외부 링크
* 
* 

분류:수론 정리