페르마 두 제곱수 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[수론]]에서 '''페르마 두 제곱수 정리'''(-數定理, {{llang|en|Fermat's theorem on sums of two squares}})는 홀수 [[소수 (수론)|소수]]가 두 개의 [[제곱수]]의 합일 필요 충분 조건이 4에 대한 나머지가 1이라는 것이라는 정리이다.

== 정의 ==
[[홀수와 짝수|홀수]] 소수 <math>p</math>가 주어졌다고 하자. '''페르마 두 제곱수 정리'''에 따르면, 다음 두 조건이 서로 동치이다.
* <math>p=x^2+y^2</math>인 정수 <math>x,y</math>가 존재한다.
* <math>p\equiv 1\pmod 4</math>

사실, 4에 대한 나머지가 1인 소수는 무한히 많이 존재하며, 이에 대한 두 제곱수로의 표현은 (더하는 순서를 무시하면) 유일하다. 작은 소수의 경우는 다음과 같다.
{| class="wikitable"
! 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이기 때문이다. 반대 방향에 대한 몇 가지 증명은 아래와 같다.

=== 오일러의 증명 ===
처음 출판된 증명은 [[레온하르트 오일러]]가 제시하였다.<ref name="Euler1758">
{{저널 인용
|url=http://eulerarchive.maa.org/pages/E228.html
|성=Euler
|이름=Leonhard
|저자링크=레온하르트 오일러
|제목=De numeris, qui sunt aggregata duorum quadratorum
|언어=la
|저널=Novi Commentarii academiae scientiarum Petropolitanae
|날짜=1758
|권=4
|쪽=3–40
}}
</ref><ref name="Euler1760">{{저널 인용
|url=http://eulerarchive.maa.org/pages/E228.html
|성=Euler
|이름=Leonhard
|저자링크=레온하르트 오일러
|제목=Demonstratio theorematis Fermatiani omnem numerum primum formae 4n+1 esse summam duorum quadratorum
|언어=la
|저널=Novi Commentarii academiae scientiarum Petropolitanae
|날짜=1760
|권=5
|쪽=3–13
}}</ref> 이 증명은 [[무한 강하법]]을 사용하며, 이후에 제시된 증명들에 비하면 복잡하다. 이는 대략 다음과 같다.

우선, 다음과 같은 명제를 증명하자.
* 어떤 두 제곱수의 합인 수 <math>a^2+b^2</math>가 두 제곱수의 합인 소인수 <math>c^2+d^2</math>를 갖는다면, 몫 <math>(a^2+b^2)/(c^2+d^2)</math>은 두 제곱수의 합이다.
가정에 의하여, 다음이 성립한다.
:<math>c^2+d^2\mid c^2(a^2+b^2)-a^2(c^2+d^2)=(bc+ad)(bc-ad)</math>
즉, <math>c^2+d^2\mid bc+ad</math>이거나, <math>c^2+d^2\mid bc-ad</math>이다. 편의상 전자를 가정하자. 그렇다면, 브라마굽타-피보나치 항등식
:<math>(a^2+b^2)(c^2+d^2)=(bc+ad)^2+(bd-ac)^2</math>
에 의하여, <math>c^2+d^2\mid bc+ad</math>이므로, 두 수의 몫은 다음과 같이 두 제곱수의 합이다.
:<math>\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</math>

이제, 다음과 같은 명제를 증명하자.
* 어떤 두 제곱수의 합인 수 <math>n</math>가 두 제곱수의 합이 아닌 약수 <math>p</math>를 갖는다면, 몫 <math>n/p</math>는 두 제곱수의 합이 아닌 약수를 갖는다.
귀류법을 사용하여, <math>n/p</math>의 모든 약수가 두 제곱수의 합이라고 하자. 그렇다면, 특히 <math>n/p</math>의 한 소인수 <math>q</math>는 두 제곱수의 합이며, 이전의 명제에 따라, <math>n/q</math>는 두 제곱수의 합이다. 이를 <math>n/p</math>의 (중복도를 감안한) 모든 소인수에 대하여 반복하면, <math>p</math>가 두 제곱수의 합이라는 결론을 얻으며, 이는 모순이다.

이제, 다음과 같은 명제를 증명하자.
* 정수 <math>a,b,p</math>가 <math>\gcd\{a,b\}=1</math>이고, <math>p\mid a^2+b^2</math>이라고 하자. 그렇다면, <math>\gcd\{c,d\}=1</math>이고, <math>p\mid c^2+d^2</math>이며, <math>c^2+d^2\le p^2/2</math>인 정수 <math>c,d</math>가 존재한다.
다음과 같은 정수 <math>c,d</math>을 취하자.
:<math>a\equiv c,\;b\equiv d\pmod p</math>
:<math>|c|,|d|\le\frac p2</math>
그렇다면, <math>\gcd\{a,b\}=1</math>이므로 <math>c^2+d^2\ne 0</math>이고, 또한
:<math>c^2+d^2\equiv a^2+b^2\equiv 0\pmod p</math>
이다. <math>g,c',d'</math>을 다음과 같이 정의하자.
:<math>g=\gcd\{c,d\},\;c'=\frac cg,\;d'=\frac dg</math>
그렇다면, <math>\gcd\{c',d'\}=1</math>이다. 또한, <math>\gcd\{a,b\}=1</math>이므로, <math>\gcd\{g,p\}=1</math>이며, <math>g^2\mid(c^2+d^2)/p</math>이다. 따라서, 다음이 성립한다.
:<math>p\mid\frac{c^2+d^2}{g^2p}\cdot p={c'}^2+{d'}^2</math>
:<math>{c'}^2+{d'}^2\le c^2+d^2\le 2\cdot\left(\frac p2\right)^2=\frac{p^2}2</math>
즉, <math>c',d'</math>는 명제의 조건을 만족시킨다.

이제, 다음과 같은 명제를 증명하자.
* 정수 <math>a,b</math>가 <math>\gcd\{a,b\}=1</math>이라면, <math>a^2+b^2</math>의 모든 약수는 두 제곱수의 합이다.
귀류법을 사용하여, <math>p\mid a^2+b^2</math>가 두 제곱수의 합이 아니라고 가정하자. 이전의 명제에 따라, 다음을 만족시키는 정수 <math>c,d</math>를 취하자.
:<math>\gcd\{c,d\}=1,\;p\mid c^2+d^2,\;c^2+d^2\le\frac{p^2}2</math>
그렇다면, <math>(c^2+d^2)/p</math>는 두 제곱수의 합이 아닌 약수 <math>q\mid(c^2+d^2)/p</math>를 갖는다. 또한 <math>q\le p/2</math>이다. 이를 <math>q</math>와 <math>c^2+d^2</math>에 대하여 반복할 수 있다. 즉, 다음을 만족시키는 정수 <math>e,f</math>를 취하자.
:<math>\gcd\{e,f\}=1,\;q\mid e^2+f^2,\;e^2+f^2\le\frac{q^2}2</math>
그렇다면, <math>(e^2+f^2)/q</math>는 두 제곱수의 합이 아닌 약수 <math>r\mid(e^2+f^2)/q</math>를 가지며, <math>r\le q/2</math>이다. 이와 같이 반복하면, 양의 정수의 순감소 무한 수열
:<math>p>q>r>\cdots</math>
를 얻으며, 이는 모순이다.

이제, 두 제곱수 정리를 증명하자. 소수 <math>p</math>가 어떤 정수 <math>n</math>에 대하여 <math>p=4n+1</math>라고 하자. 다음과 같은 정수 <math>a,b</math>가 존재한다고 가정하자.
:<math>\gcd\{a,b\}=1</math>
:<math>p\nmid a,b,a^{2n}-b^{2n}</math>
그렇다면, [[페르마 소정리]]에 따라,
:<math>p\mid a^{4n}-b^{4n}</math>
이다. 따라서
:<math>p\mid a^{2n}+b^{2n}</math>
이며, 이전의 명제에 따라 <math>p</math>는 두 제곱수의 합이다. 즉, 두 제곱수 정리를 증명하려면 위와 같은 <math>a,b</math>를 찾으면 된다.

이를 위해, 수열
:<math>(1^{2n},2^{2n},\dots,(2n+1)^{2n})</math>
의 1계 유한 차분
:<math>(2^{2n}-1^{2n},3^{2n}-2^{2n},\dots,(2n+1)^{2n}-(2n)^{2n})</math>
을 생각하자. 귀류법을 사용하여, 1계 유한 [[차분]]의 모든 항이 <math>p</math>를 약수로 가진다고 가정하자. 그렇다면, 2계 유한 차분의 모든 항 역시 <math>p</math>를 약수로 가지며, 마찬가지로 3계, 4계, …, <math>2n</math>계 유한 차분의 모든 항 역시 <math>p</math>를 약수로 가진다. 그러나 수열 <math>1^{2n},2^{2n},\dots,(2n+1)^{2n}</math>의 <math>2n</math>계 유한 차분은 모든 항이 <math>(2n)!</math>이며, <math>p</math>는 <math>(2n)!</math>의 약수가 아니다. 이는 모순이므로, 어떤 <math>b\in\{1,\dots,2n\}</math>에 대하여
:<math>p\nmid(b+1)^{2n}-b^{2n}</math>
이 성립한다. 즉, <math>b</math>와 <math>a=b+1</math>은 위와 같은 조건을 만족시킨다.

=== 투에 보조정리를 통한 증명 ===
만약 <math>p\equiv 1\pmod 4</math>라고 하자.<ref name="오정환">{{서적 인용|저자1=오정환|저자2=이준복|제목=정수론|날짜=2003}}</ref>{{rp|167-168}} 그렇다면, −1은 <math>p</math>에 대한 [[제곱 잉여]]이므로,
:<math>a^2\equiv-1\pmod p</math>
인 정수 <math>a</math>가 존재한다. 또한 <math>\gcd\{p,a\}=1</math>이므로, [[투에 보조정리]]에 따라,
:<math>ax\equiv y\pmod p</math>
:<math>0<|x|,|y|<\sqrt p</math>
를 만족시키는 정수 <math>x,y</math>가 존재한다. 따라서,
:<math>y^2\equiv(ax)^2\equiv-x^2\pmod p</math>
이며, <math>p\mid x^2+y^2</math>이다. 또한, <math>0<x^2+y^2<2p</math>이므로,
:<math>x^2+y^2=p</math>
이다.

=== “한 문장” 증명 ===
유한 집합<ref name="Zagier">{{저널 인용
|성=Zagier
|이름=D.
|제목=A One-Sentence Proof that Every Prime p≡1(mod4) is a Sum of Two Squares
|url=https://archive.org/details/sim_american-mathematical-monthly_1990-02_97_2/page/n41
|언어=en
|저널=The American Mathematical Monthly
|권=97
|호=2
|쪽=144
|날짜=1990-02
|issn=0002-9890
|doi=10.2307/2323918
|jstor=2323918
}}</ref>{{rp|144}}
:<math>S=\{(x,y,z)\in\mathbb N^3\colon p=x^2+4yz\}</math>
위의 [[대합 (수학)|대합]]
:<math>(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
</math>
는 유일한 [[고정점]] <math>(1,1,(p-1)/4)</math>를 가지므로, <math>|S|</math>는 홀수이다. 따라서 또 하나의 대합
:<math>(x,y,z)\mapsto(x,z,y)\qquad\forall(x,y,z)\in S</math>
역시 적어도 하나의 고정점 <math>(x,y,y)</math>을 가지며, 이는
:<math>x^2+(2y)^2=p</math>
를 만족시킨다.

== 일반화 ==
=== <math>n=x^2+y^2</math> ===
임의의 양의 정수 <math>n</math>에 대하여, 다음 두 조건이 서로 동치이다.
* <math>n=x^2+y^2</math>인 정수 <math>x,y</math>가 존재한다.
* <math>n</math>은 4에 대한 나머지가 3인 홀수 중복도의 소인수를 가지지 않는다.
충분 조건은 어떤 두 제곱수의 합으로 표현되는 수의 곱도 두 제곱수의 합임을 이용하면 자명하다. 필요 조건의 증명에는 제곱 잉여의 이론을 이용하면 쉽게 증명할 수 있다.

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

==== 증명 ====
우선, <math>p=x^2+2y^2</math>인 정수 <math>x,y</math>가 존재한다고 가정하자.<ref name="Deza">{{서적 인용
|성1=Deza
|이름1=Elena
|성2=Deza
|이름2=Michel Marie
|제목=Figurate Numbers
|언어=en
|출판사=World Scientific
|날짜=2012
|isbn=978-981-4355-48-3
}}</ref>{{rp|321–322}} 그렇다면,
:<math>\gcd\{p,x\}=\gcd\{p,y\}=1</math>
이므로, 어떤 정수 <math>z</math>에 대하여
:<math>yz\equiv x\pmod p</math>
가 성립한다. 따라서,
:<math>0\equiv x^2+2y^2\equiv y^2(z^2+2)\pmod p</math>
이므로,
:<math>z^2\equiv-2\pmod p</math>
이다. 즉, −2는 <math>p</math>에 대한 제곱 잉여이며, 이는
:<math>p\equiv 1,3\pmod 8</math>
와 동치이다.

반대로,
:<math>p\equiv 1,3\pmod 8</math>
라고 가정하자. 이는 −2가 <math>p</math>에 대한 제곱 잉여인 것과 동치이므로, 어떤 정수 <math>z</math>에 대하여
:<math>z^2\equiv-2\pmod p</math>
가 성립한다. 다음과 같은 집합을 생각하자.
:<math>\{\phi_p(rz+s)\colon r,s\in\{0,1,\dots,\lfloor\sqrt p\rfloor\}\}\subseteq\mathbb Z/(p)</math>
여기서 <math>\phi_p(-)</math>는 <math>p</math>에 대한 나머지를 구하는 함수이다. 이 집합의 원소는 많아야 <math>p</math>개여야 하므로, 다음을 만족시키는 <math>r,r',s,s'\in\{0,1,\dots,\lfloor\sqrt p\rfloor\}</math>가 존재한다.
:<math>(r,s)\ne(r',s')</math>
:<math>rz+s\equiv r'z+s'\pmod p</math>
사실, 다음과 같은 [[동치]] 관계에 따라, <math>r\ne r'</math>이며 <math>s\ne s'</math>이다.
:<math>\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}</math>
이제, 정수 <math>x,y</math>를 다음과 같이 정의하자.
:<math>x=|s-s'|,\;y=|r-r'|</math>
그렇다면,
:<math>yz\equiv\pm x\pmod p</math>
:<math>0<x,y<\sqrt p</math>
이며,
:<math>0\equiv y^2(z^2+2)\equiv x^2+2y^2\pmod p</math>
이다. 즉, 다음을 만족시키는 정수 <math>m</math>이 존재한다.
:<math>mp=x^2+2y^2</math>
또한, <math>0<x^2+2y^2<3p</math>이므로, <math>m\in\{1,2\}</math>이다. 만약 <math>m=1</math>이라면, <math>p</math>는 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다. 만약 <math>m=2</math>이라면, <math>2\mid x</math>이며,
:<math>p=y^2+2\left(\frac x2\right)^2</math>
이므로, 역시 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다.

=== <math>n=x^2+2y^2</math> ===
양의 정수 <math>n</math>에 대하여, 다음 두 조건이 서로 동치이다.
* <math>n=x^2+2y^2</math>인 정수 <math>x,y</math>가 존재한다.
* <math>n</math>은 8에 대한 나머지가 5, 7인 홀수 중복도의 소인수를 가지지 않는다.

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

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

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=Fermats4nPlus1Theorem|title=Fermat's 4n+1 theorem}}

[[분류:수론 정리]]