페르마 두 제곱수 정리

틀:위키데이터 속성 추적 수론에서 페르마 두 제곱수 정리(-數定理, 틀:Llang)는 홀수 소수가 두 개의 제곱수의 합일 필요 충분 조건이 4에 대한 나머지가 1이라는 것이라는 정리이다.

정의

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

• $p=x^2+y^2$인 정수 $x,y$가 존재한다.
• $p\equiv 1(\mathrm{mod}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	틀:OEIS	틀:OEIS

증명

전자가 후자를 함의하는 것은 자명하다. 이는 제곱수의 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\le p^2/2$인 정수 $c,d$가 존재한다.

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

$a\equiv c,b\equiv d(\mathrm{mod}p)$

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

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

$c^2+d^2\equiv a^2+b^2\equiv 0(\mathrm{mod}p)$

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

$g=\gcd \{c,d\},c^{\prime }=\frac{c}{g},d^{\prime }=\frac{d}{g}$

그렇다면, $\gcd \{c^{\prime },d^{\prime }\}=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^{\prime }}^2+{d^{\prime }}^2$

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

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

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

• 정수 $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$은 위와 같은 조건을 만족시킨다.

투에 보조정리를 통한 증명

만약 $p\equiv 1(\mathrm{mod}4)$라고 하자.틀:Rp 그렇다면, −1은 $p$에 대한 제곱 잉여이므로,

$a^2\equiv -1(\mathrm{mod}p)$

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

$ax\equiv y(\mathrm{mod}p)$

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

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

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

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

$x^2+y^2=p$

이다.

“한 문장” 증명

유한 집합틀:Rp

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

위의 대합

$(x,y,z)\mapsto \{\begin{array}{cc}(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{array}\mathrm{\forall }(x,y,z)\in S$

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

$(x,y,z)\mapsto (x,z,y)\mathrm{\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(\mathrm{mod}8)$

증명

우선, $p=x^2+2y^2$인 정수 $x,y$가 존재한다고 가정하자.틀:Rp 그렇다면,

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

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

$yz\equiv x(\mathrm{mod}p)$

가 성립한다. 따라서,

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

이므로,

$z^2\equiv -2(\mathrm{mod}p)$

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

$p\equiv 1,3(\mathrm{mod}8)$

와 동치이다.

반대로,

$p\equiv 1,3(\mathrm{mod}8)$

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

$z^2\equiv -2(\mathrm{mod}p)$

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

$\{{\varphi }_p(rz+s):r,s\in \{0,1,\dots ,\lfloor \sqrt{p}\rfloor \}\}\subseteq \mathbb{Z}/(p)$

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

$(r,s)\ne (r^{\prime },s^{\prime })$

$rz+s\equiv r^{\prime }z+s^{\prime }(\mathrm{mod}p)$

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

$\begin{array}{cc}r=r^{\prime }& ⟺r-r^{\prime }\equiv 0(\mathrm{mod}p)\\ & ⟺(r-r^{\prime })z\equiv 0(\mathrm{mod}p)\\ & ⟺s-s^{\prime }\equiv 0(\mathrm{mod}p)\\ & ⟺s=s^{\prime }\end{array}$

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

$x=|s-s^{\prime }|,y=|r-r^{\prime }|$

그렇다면,

$yz\equiv \pm x(\mathrm{mod}p)$

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

이며,

$0\equiv y^2(z^2+2)\equiv x^2+2y^2(\mathrm{mod}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년 스위스 수학자 레온하르트 오일러가 크리스티안 골트바흐에게 보내는 편지에서였다.

같이 보기

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

외부 링크

• 틀:매스월드