전자가 후자를 함의하는 것은 자명하다. 이는 제곱수의 4에 대한 나머지는 0이거나 1이므로, 두 제곱수의 합의 4에 대한 나머지는 0, 1, 2이기 때문이다. 반대 방향에 대한 몇 가지 증명은 아래와 같다.
오일러의 증명
편집
처음 출판된 증명은 레온하르트 오일러 가 제시하였다.[1] [2] 무한 강하법 을 사용하며, 이후에 제시된 증명들에 비하면 복잡하다. 이는 대략 다음과 같다.
우선, 다음과 같은 명제를 증명하자.
어떤 두 제곱수의 합인 수
a
2
+
b
2
{\displaystyle a^{2}+b^{2}}
c
2
+
d
2
{\displaystyle c^{2}+d^{2}}
(
a
2
+
b
2
)
/
(
c
2
+
d
2
)
{\displaystyle (a^{2}+b^{2})/(c^{2}+d^{2})}
가정에 의하여, 다음이 성립한다.
c
2
+
d
2
∣
c
2
(
a
2
+
b
2
)
−
a
2
(
c
2
+
d
2
)
=
(
b
c
+
a
d
)
(
b
c
−
a
d
)
{\displaystyle 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
∣
b
c
+
a
d
{\displaystyle c^{2}+d^{2}\mid bc+ad}
c
2
+
d
2
∣
b
c
−
a
d
{\displaystyle c^{2}+d^{2}\mid bc-ad}
(
a
2
+
b
2
)
(
c
2
+
d
2
)
=
(
b
c
+
a
d
)
2
+
(
b
d
−
a
c
)
2
{\displaystyle (a^{2}+b^{2})(c^{2}+d^{2})=(bc+ad)^{2}+(bd-ac)^{2}}
에 의하여,
c
2
+
d
2
∣
b
c
+
a
d
{\displaystyle c^{2}+d^{2}\mid bc+ad}
a
2
+
b
2
c
2
+
d
2
=
(
b
c
+
a
d
c
2
+
d
2
)
2
+
(
b
d
−
a
c
c
2
+
d
2
)
2
{\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}}
이제, 다음과 같은 명제를 증명하자.
어떤 두 제곱수의 합인 수
n
{\displaystyle n}
p
{\displaystyle p}
n
/
p
{\displaystyle n/p}
귀류법을 사용하여,
n
/
p
{\displaystyle n/p}
n
/
p
{\displaystyle n/p}
q
{\displaystyle q}
n
/
q
{\displaystyle n/q}
n
/
p
{\displaystyle n/p}
p
{\displaystyle p}
이제, 다음과 같은 명제를 증명하자.
정수
a
,
b
,
p
{\displaystyle a,b,p}
gcd
{
a
,
b
}
=
1
{\displaystyle \gcd\{a,b\}=1}
p
∣
a
2
+
b
2
{\displaystyle p\mid a^{2}+b^{2}}
gcd
{
c
,
d
}
=
1
{\displaystyle \gcd\{c,d\}=1}
p
∣
c
2
+
d
2
{\displaystyle p\mid c^{2}+d^{2}}
c
2
+
d
2
≤
p
2
/
2
{\displaystyle c^{2}+d^{2}\leq p^{2}/2}
c
,
d
{\displaystyle c,d}
다음과 같은 정수
c
,
d
{\displaystyle c,d}
a
≡
c
,
b
≡
d
(
mod
p
)
{\displaystyle a\equiv c,\;b\equiv d{\pmod {p}}}
|
c
|
,
|
d
|
≤
p
2
{\displaystyle |c|,|d|\leq {\frac {p}{2}}}
그렇다면,
gcd
{
a
,
b
}
=
1
{\displaystyle \gcd\{a,b\}=1}
c
2
+
d
2
≠
0
{\displaystyle c^{2}+d^{2}\neq 0}
c
2
+
d
2
≡
a
2
+
b
2
≡
0
(
mod
p
)
{\displaystyle c^{2}+d^{2}\equiv a^{2}+b^{2}\equiv 0{\pmod {p}}}
이다.
g
,
c
′
,
d
′
{\displaystyle g,c',d'}
g
=
gcd
{
c
,
d
}
,
c
′
=
c
g
,
d
′
=
d
g
{\displaystyle g=\gcd\{c,d\},\;c'={\frac {c}{g}},\;d'={\frac {d}{g}}}
그렇다면,
gcd
{
c
′
,
d
′
}
=
1
{\displaystyle \gcd\{c',d'\}=1}
gcd
{
a
,
b
}
=
1
{\displaystyle \gcd\{a,b\}=1}
gcd
{
g
,
p
}
=
1
{\displaystyle \gcd\{g,p\}=1}
g
2
∣
(
c
2
+
d
2
)
/
p
{\displaystyle g^{2}\mid (c^{2}+d^{2})/p}
p
∣
c
2
+
d
2
g
2
p
⋅
p
=
c
′
2
+
d
′
2
{\displaystyle p\mid {\frac {c^{2}+d^{2}}{g^{2}p}}\cdot p={c'}^{2}+{d'}^{2}}
c
′
2
+
d
′
2
≤
c
2
+
d
2
≤
2
⋅
(
p
2
)
2
=
p
2
2
{\displaystyle {c'}^{2}+{d'}^{2}\leq c^{2}+d^{2}\leq 2\cdot \left({\frac {p}{2}}\right)^{2}={\frac {p^{2}}{2}}}
즉,
c
′
,
d
′
{\displaystyle c',d'}
이제, 다음과 같은 명제를 증명하자.
정수
a
,
b
{\displaystyle a,b}
gcd
{
a
,
b
}
=
1
{\displaystyle \gcd\{a,b\}=1}
a
2
+
b
2
{\displaystyle a^{2}+b^{2}}
귀류법을 사용하여,
p
∣
a
2
+
b
2
{\displaystyle p\mid a^{2}+b^{2}}
c
,
d
{\displaystyle c,d}
gcd
{
c
,
d
}
=
1
,
p
∣
c
2
+
d
2
,
c
2
+
d
2
≤
p
2
2
{\displaystyle \gcd\{c,d\}=1,\;p\mid c^{2}+d^{2},\;c^{2}+d^{2}\leq {\frac {p^{2}}{2}}}
그렇다면,
(
c
2
+
d
2
)
/
p
{\displaystyle (c^{2}+d^{2})/p}
q
∣
(
c
2
+
d
2
)
/
p
{\displaystyle q\mid (c^{2}+d^{2})/p}
q
≤
p
/
2
{\displaystyle q\leq p/2}
q
{\displaystyle q}
c
2
+
d
2
{\displaystyle c^{2}+d^{2}}
e
,
f
{\displaystyle e,f}
gcd
{
e
,
f
}
=
1
,
q
∣
e
2
+
f
2
,
e
2
+
f
2
≤
q
2
2
{\displaystyle \gcd\{e,f\}=1,\;q\mid e^{2}+f^{2},\;e^{2}+f^{2}\leq {\frac {q^{2}}{2}}}
그렇다면,
(
e
2
+
f
2
)
/
q
{\displaystyle (e^{2}+f^{2})/q}
r
∣
(
e
2
+
f
2
)
/
q
{\displaystyle r\mid (e^{2}+f^{2})/q}
r
≤
q
/
2
{\displaystyle r\leq q/2}
p
>
q
>
r
>
⋯
{\displaystyle p>q>r>\cdots }
를 얻으며, 이는 모순이다.
이제, 두 제곱수 정리를 증명하자. 소수
p
{\displaystyle p}
n
{\displaystyle n}
p
=
4
n
+
1
{\displaystyle p=4n+1}
a
,
b
{\displaystyle a,b}
gcd
{
a
,
b
}
=
1
{\displaystyle \gcd\{a,b\}=1}
p
∤
a
,
b
,
a
2
n
−
b
2
n
{\displaystyle p\nmid a,b,a^{2n}-b^{2n}}
그렇다면, 페르마 소정리 에 따라,
p
∣
a
4
n
−
b
4
n
{\displaystyle p\mid a^{4n}-b^{4n}}
이다. 따라서
p
∣
a
2
n
+
b
2
n
{\displaystyle p\mid a^{2n}+b^{2n}}
이며, 이전의 명제에 따라
p
{\displaystyle p}
a
,
b
{\displaystyle a,b}
이를 위해, 수열
(
1
2
n
,
2
2
n
,
…
,
(
2
n
+
1
)
2
n
)
{\displaystyle (1^{2n},2^{2n},\dots ,(2n+1)^{2n})}
의 1계 유한 차분
(
2
2
n
−
1
2
n
,
3
2
n
−
2
2
n
,
…
,
(
2
n
+
1
)
2
n
−
(
2
n
)
2
n
)
{\displaystyle (2^{2n}-1^{2n},3^{2n}-2^{2n},\dots ,(2n+1)^{2n}-(2n)^{2n})}
을 생각하자. 귀류법을 사용하여, 1계 유한 차분 의 모든 항이
p
{\displaystyle p}
p
{\displaystyle p}
2
n
{\displaystyle 2n}
p
{\displaystyle p}
1
2
n
,
2
2
n
,
…
,
(
2
n
+
1
)
2
n
{\displaystyle 1^{2n},2^{2n},\dots ,(2n+1)^{2n}}
2
n
{\displaystyle 2n}
(
2
n
)
!
{\displaystyle (2n)!}
p
{\displaystyle p}
(
2
n
)
!
{\displaystyle (2n)!}
b
∈
{
1
,
…
,
2
n
}
{\displaystyle b\in \{1,\dots ,2n\}}
p
∤
(
b
+
1
)
2
n
−
b
2
n
{\displaystyle p\nmid (b+1)^{2n}-b^{2n}}
이 성립한다. 즉,
b
{\displaystyle b}
a
=
b
+
1
{\displaystyle a=b+1}
투에 보조정리를 통한 증명
편집
만약
p
≡
1
(
mod
4
)
{\displaystyle p\equiv 1{\pmod {4}}}
[3] :167-168
p
{\displaystyle p}
제곱 잉여 이므로,
a
2
≡
−
1
(
mod
p
)
{\displaystyle a^{2}\equiv -1{\pmod {p}}}
인 정수
a
{\displaystyle a}
gcd
{
p
,
a
}
=
1
{\displaystyle \gcd\{p,a\}=1}
투에 보조정리 에 따라,
a
x
≡
y
(
mod
p
)
{\displaystyle ax\equiv y{\pmod {p}}}
0
<
|
x
|
,
|
y
|
<
p
{\displaystyle 0<|x|,|y|<{\sqrt {p}}}
를 만족시키는 정수
x
,
y
{\displaystyle x,y}
y
2
≡
(
a
x
)
2
≡
−
x
2
(
mod
p
)
{\displaystyle y^{2}\equiv (ax)^{2}\equiv -x^{2}{\pmod {p}}}
이며,
p
∣
x
2
+
y
2
{\displaystyle p\mid x^{2}+y^{2}}
0
<
x
2
+
y
2
<
2
p
{\displaystyle 0<x^{2}+y^{2}<2p}
x
2
+
y
2
=
p
{\displaystyle x^{2}+y^{2}=p}
이다.
한 문장 증명
편집
유한 집합[4] :144
S
=
{
(
x
,
y
,
z
)
∈
N
3
:
p
=
x
2
+
4
y
z
}
{\displaystyle S=\{(x,y,z)\in \mathbb {N} ^{3}\colon p=x^{2}+4yz\}}
위의 대합
(
x
,
y
,
z
)
↦
{
(
x
+
2
z
,
z
,
y
−
x
−
z
)
x
<
y
−
z
(
2
y
−
x
,
y
,
x
−
y
+
z
)
y
−
z
<
x
<
2
y
(
x
−
2
y
,
x
−
y
+
z
,
y
)
x
>
2
y
∀
(
x
,
y
,
z
)
∈
S
{\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}
는 유일한 고정점
(
1
,
1
,
(
p
−
1
)
/
4
)
{\displaystyle (1,1,(p-1)/4)}
|
S
|
{\displaystyle |S|}
(
x
,
y
,
z
)
↦
(
x
,
z
,
y
)
∀
(
x
,
y
,
z
)
∈
S
{\displaystyle (x,y,z)\mapsto (x,z,y)\qquad \forall (x,y,z)\in S}
역시 적어도 하나의 고정점
(
x
,
y
,
y
)
{\displaystyle (x,y,y)}
x
2
+
(
2
y
)
2
=
p
{\displaystyle x^{2}+(2y)^{2}=p}
를 만족시킨다.
n
=
x
2
+
y
2
{\displaystyle n=x^{2}+y^{2}}
편집
임의의 양의 정수
n
{\displaystyle n}
n
=
x
2
+
y
2
{\displaystyle n=x^{2}+y^{2}}
x
,
y
{\displaystyle x,y}
n
{\displaystyle n}
충분 조건은 어떤 두 제곱수의 합으로 표현되는 수의 곱도 두 제곱수의 합임을 이용하면 자명하다. 필요 조건의 증명에는 제곱 잉여의 이론을 이용하면 쉽게 증명할 수 있다.
p
=
x
2
+
2
y
2
{\displaystyle p=x^{2}+2y^{2}}
편집
홀수 소수
p
{\displaystyle p}
p
=
x
2
+
2
y
2
{\displaystyle p=x^{2}+2y^{2}}
x
,
y
{\displaystyle x,y}
p
≡
1
,
3
(
mod
8
)
{\displaystyle p\equiv 1,3{\pmod {8}}}
우선,
p
=
x
2
+
2
y
2
{\displaystyle p=x^{2}+2y^{2}}
x
,
y
{\displaystyle x,y}
[5] :321–322
gcd
{
p
,
x
}
=
gcd
{
p
,
y
}
=
1
{\displaystyle \gcd\{p,x\}=\gcd\{p,y\}=1}
이므로, 어떤 정수
z
{\displaystyle z}
y
z
≡
x
(
mod
p
)
{\displaystyle yz\equiv x{\pmod {p}}}
가 성립한다. 따라서,
0
≡
x
2
+
2
y
2
≡
y
2
(
z
2
+
2
)
(
mod
p
)
{\displaystyle 0\equiv x^{2}+2y^{2}\equiv y^{2}(z^{2}+2){\pmod {p}}}
이므로,
z
2
≡
−
2
(
mod
p
)
{\displaystyle z^{2}\equiv -2{\pmod {p}}}
이다. 즉, −2는
p
{\displaystyle p}
p
≡
1
,
3
(
mod
8
)
{\displaystyle p\equiv 1,3{\pmod {8}}}
와 동치이다.
반대로,
p
≡
1
,
3
(
mod
8
)
{\displaystyle p\equiv 1,3{\pmod {8}}}
라고 가정하자. 이는 −2가
p
{\displaystyle p}
z
{\displaystyle z}
z
2
≡
−
2
(
mod
p
)
{\displaystyle z^{2}\equiv -2{\pmod {p}}}
가 성립한다. 다음과 같은 집합을 생각하자.
{
ϕ
p
(
r
z
+
s
)
:
r
,
s
∈
{
0
,
1
,
…
,
⌊
p
⌋
}
}
⊆
Z
/
(
p
)
{\displaystyle \{\phi _{p}(rz+s)\colon r,s\in \{0,1,\dots ,\lfloor {\sqrt {p}}\rfloor \}\}\subseteq \mathbb {Z} /(p)}
여기서
ϕ
p
(
−
)
{\displaystyle \phi _{p}(-)}
p
{\displaystyle p}
p
{\displaystyle p}
r
,
r
′
,
s
,
s
′
∈
{
0
,
1
,
…
,
⌊
p
⌋
}
{\displaystyle r,r',s,s'\in \{0,1,\dots ,\lfloor {\sqrt {p}}\rfloor \}}
(
r
,
s
)
≠
(
r
′
,
s
′
)
{\displaystyle (r,s)\neq (r',s')}
r
z
+
s
≡
r
′
z
+
s
′
(
mod
p
)
{\displaystyle rz+s\equiv r'z+s'{\pmod {p}}}
사실, 다음과 같은 동치 관계에 따라,
r
≠
r
′
{\displaystyle r\neq r'}
s
≠
s
′
{\displaystyle s\neq s'}
r
=
r
′
⟺
r
−
r
′
≡
0
(
mod
p
)
⟺
(
r
−
r
′
)
z
≡
0
(
mod
p
)
⟺
s
−
s
′
≡
0
(
mod
p
)
⟺
s
=
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}}}
이제, 정수
x
,
y
{\displaystyle x,y}
x
=
|
s
−
s
′
|
,
y
=
|
r
−
r
′
|
{\displaystyle x=|s-s'|,\;y=|r-r'|}
그렇다면,
y
z
≡
±
x
(
mod
p
)
{\displaystyle yz\equiv \pm x{\pmod {p}}}
0
<
x
,
y
<
p
{\displaystyle 0<x,y<{\sqrt {p}}}
이며,
0
≡
y
2
(
z
2
+
2
)
≡
x
2
+
2
y
2
(
mod
p
)
{\displaystyle 0\equiv y^{2}(z^{2}+2)\equiv x^{2}+2y^{2}{\pmod {p}}}
이다. 즉, 다음을 만족시키는 정수
m
{\displaystyle m}
m
p
=
x
2
+
2
y
2
{\displaystyle mp=x^{2}+2y^{2}}
또한,
0
<
x
2
+
2
y
2
<
3
p
{\displaystyle 0<x^{2}+2y^{2}<3p}
m
∈
{
1
,
2
}
{\displaystyle m\in \{1,2\}}
m
=
1
{\displaystyle m=1}
p
{\displaystyle p}
m
=
2
{\displaystyle m=2}
2
∣
x
{\displaystyle 2\mid x}
p
=
y
2
+
2
(
x
2
)
2
{\displaystyle p=y^{2}+2\left({\frac {x}{2}}\right)^{2}}
이므로, 역시 어떤 제곱수와 다른 어떤 제곱수의 2배의 합이다.
n
=
x
2
+
2
y
2
{\displaystyle n=x^{2}+2y^{2}}
편집
양의 정수
n
{\displaystyle n}
n
=
x
2
+
2
y
2
{\displaystyle n=x^{2}+2y^{2}}
x
,
y
{\displaystyle x,y}
n
{\displaystyle n}
