소수를 4로 나눈 나머지가 1이 되는 필요충분조건
정리
$p \ne 2$ 가 소수라고 하자.
$p \equiv 1 \pmod{4}$ $\iff$ 어떤 $a,b \in \mathbb{Z}$ 에 대해 $p = a^2 + b^2$
설명
$p=2$ 는 제외했지만, 사실 $ 2= 1^2 + 1^2$ 이므로 정리에 포함되어도 큰 상관은 없다.
예를들어 $13 \equiv 1 \pmod{4}$ 는 $$ 13 = 4 + 9 = 2^2 + 3^2 $$ $37 \equiv 1 \pmod{4}$ 는 $$ 37 = 1 + 36 = 1^2 + 6^2 $$ $61 \equiv 1 \pmod{4}$ 는 $$ 61 = 25 + 36 = 5^2 + 6^2 $$ 이다. 이러한 팩트는 그 자체만으로도 흥미롭지만, 가우스 소수와 깊은 연관이 있어 정수론을 한 차원 높은 곳으로 이끈다.
증명
$( \implies )$
Part 1.
$p \equiv 1 \pmod{4}$ 이므로 어떤 $k \in \mathbb{N}$ 에 대해 $p = 4k +1$ 으로 나타낼 수 있다.
오일러 판정법: $\displaystyle a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}$
오일러 판정법에 의해 $$ \left( {{-1} \over {p}} \right) \equiv (-1)^{ {{ (4k + 1 ) - 1 } \over {2}} } \equiv (-1)^{2k} \equiv 1 \pmod{p} $$ 따라서 $-1$ 은 $p$ 에서 이차잉여고, $c^{2} \equiv -1 \pmod{p}$ 를 만족하는 $c \in \mathbb{Z}$ 가 존재한다. 양변에 $B^2$ 을 곱하고 이항하면 $$ (cB)^2 + B^2 \equiv 0 \pmod{ p } $$ 이다. $A := (cB)$ 이라 두면 어떤 $M \in \mathbb{Z}$ 에 대해 $$ A^2 + B^2 = Mp $$ 이고 $$ M = {{ A^2 + B^2 } \over {p}} \le {{ (p-1)^2 + 1^2 } \over {p}} = p - {{ 2p - 2 } \over {p}} < p $$ 이므로 $M < p$ 이다. 이 $M$ 을 계속 줄여서 $M=1$ 이 되면 어떤 $a,b \in \mathbb{Z}$ 에 대해 $p = a^2 + b^2$ 이라고 할 수 있다.
Part 2. $1 \le r < M$
$$ u \equiv A \pmod{M} \\ v \equiv B \pmod{M} \\ - {{M} \over {2}} \le u,v \le {{M} \over {2}} $$ 을 만족하는 $u,v \in \mathbb{Z}$ 를 생각해보자(예를 들어 $M=13$ 이고 $A \equiv 10 \pmod{13}$ 이면 $u \equiv -3 \pmod{13}$ 이므로 그 존재성은 항상 보장되어있다). 그러면 Part 1에서 $A^2 + B^2 = pM$ 이었으므로 $$ u^2 + v^2 \equiv A^2 + B^2 \equiv 0 \pmod{M} $$ 이고, 어떤 $r \in \mathbb{Z}$ 에 대해 $u^2 + v^2 = rM$ 이다. 또한 $$ r = {{ u^2 + v^2 } \over {M}} \le {{ (M/2)^2 + (M/2)^2 } \over { M }} = { { M } \over { 2 } } < M $$ 이므로 $r < M$ 이다.
여기서 $r = 0$ 이라고 가정하면 $\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$ 이므로 $A, B$ 는 $M$ 의 배수고 $A^2 + B^2$ 는 $M^2$ 의 배수여야한다. 즉 $M$ 이 $p$ 의 배수여야하는데 Part 1에서 $M < p$ 임을 보였으므로 이는 불가능하고, $r$ 은 적어도 $0$ 보다는 커야한다. 정리하면 $1 \le r < M$ 이다.
Part 3.
코시-슈바르츠 등식에 따라 $$ \begin{align*} & (u^2 + v^2) ( A^2 + B^2 ) \\ =& u^2 A^2 + v^2 A^2 + u^2 B^2 + v^2 B^2 \\ =& ( u^2 A^2 + 2uAvB + v^2 B^2 ) + ( v^2 A^2 - 2uAvB + u^2 B^2 ) \\ =& ( uA + vB )^2 + ( uA - vB )^2 \\ =& ( uA - vB ) \\ \equiv& BA - AB \pmod{M} \\ \equiv& 0 \pmod{M} \end{align*} $$ 이므로 $( uA - vB )$ 은 $M$ 의 배수다. 또한 위의 Part 2에서 $( uA + vB ) \equiv AA + BB \equiv 0 \pmod{M}$ 이므로 $( uA + vB )$ 도 $M$ 의 배수다.
Part 4.
$A^2 + B^2 = Mp$ 이고 $u^2 + v^2 = Mr$ 이므로 $$ (u^2 + v^2) ( A^2 + B^2 ) = M^2 r p $$ 이고, 코시-슈바르츠 등식을 이용하면 $$ ( uA + vB )^2 + ( uA - vB )^2 = M^2 r p $$ 을 얻는다. 위의 Part 3에서 $( uA + vB )$ 와 $( uA - vB )$ 은 $M$ 의 배수이므로 양변을 $M^2$ 으로 나누면 $$ \left( {{ uA + vB } \over {M}} \right)^2 + \left( {{ uA - vB } \over {M}} \right)^2 = r p $$ 이에 대해 새로운 $$ A_{2} : = \left( {{ uA + vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r $$ 을 정의하면, 다시 $$ A_{2}^{2} + B_{2}^{2} = M_{2} p $$ 을 얻는다. 따라서 $k \in \mathbb{N}$ 에 대해 이러한 $A_{k}, B_{k}, M_{k}$ 은 Part 1~3에서 정의했던 $A, B, M$ 과 같은 성질을 가진다.
위의 Part 2에서 $r < M$ 이었으므로 $M_{k}$ 는 $k$ 가 증가할 때마다 작아지고, $1 \le r$ 이므로 정확히 $M=1$ 에서 멈춘다.
$( \impliedby )$
$p=a^2 + b^2$ 은 홀수이므로 $a$ 와 $b$ 가 모두 짝수거나 홀수일 수는 없다.
어떤 $n , m \in \mathbb{Z}$ 에 대해 $a := 2n +1 $, $b = 2m$ 이라고 하자. 그러면 $$ \begin{align*} p =& a^2 + b^2 \\ =& 4n^2 + 4n + 1 + 4m^2 \\ =& 4 ( n^2 + n + m ) +1 \end{align*} $$ 이므로, $p \equiv 1 \pmod{4}$ 이다.
■
위의 코시-슈바르츠 등식을 응용하고 몇가지 조건만 더 추가하면 자연수에 대해서도 비슷한 따름정리도 얻을 수 있다.
따름정리
홀수 $m$ 의 모든 소수 약수를 $4$ 로 나눈 나머지가 $1$ 이거나, 짝수 $m$ 에 대해 $\displaystyle {{m} \over {2}}$ 이 홀수고 $\displaystyle {{m} \over {2}}$ 의 모든 소수 약수를 $4$ 로 나눈 나머지가 $1$ $\iff$ $\gcd ( a,b) =1$ 을 만족하는 $a,b \in \mathbb{Z}$ 에 대해 $m = a^2 + b^2$