소수를 3으로 나눈 나머지가 1이 되는 필요충분조건
정리
$p \ne 3$ 이 소수라고 하자. $p \equiv 1 \pmod{3}$ $\iff$ 어떤 $a,b \in \mathbb{Z}$ 에 대해 $p = a^2 - ab + b^2$
설명
$p=3$ 은 제외했지만, 사실 $ 3= 2^2 - 2 \cdot 1 + 1^2$ 이므로 정리에 포함되어도 큰 상관은 없다.
예를들어 $13 \equiv 1 \pmod{4}$ 는 $$ 13 = 1 - 4 + 16 = 1^2 - 1 \cdot 4 + 4^2 $$ $37 \equiv 1 \pmod{4}$ 는 $$ 37 = 9 -21 + 49 = 3^2 - 3 \cdot 7+ 7^2 $$ $61 \equiv 1 \pmod{4}$ 는 $$ 61 = 16 - 36 + 81 = 4^2 - 4 \cdot 9 + 9^2 $$
이러한 팩트는 그 자체만으로도 흥미롭지만, 아이젠슈타인 정수와 깊은 연관이 있어 정수론을 한 차원 높은 곳으로 이끈다.
증명
$( \implies )$
$$ a^2 + 3 b^2 = ( a + b )^2 - ( a+ b) ( a - b) + (a - b) ^2 $$ 이므로, $p = a^2 + 3b^2$ 을 만족하는 $a,b \in \mathbb{Z}$ 가 존재함을 보이면 된다.
Part 1.
$p \equiv 1 \pmod{3}$ 이고 홀수이므로 어떤 $k \in \mathbb{N}$ 에 대해 $p = 6k +1$ 으로 나타낼 수 있다.
Part 1-1. 가우스의 이차상호 법칙
가우스의 이차상호 법칙: 서로 다른 두 홀수 $p , q$ 에 대해
- [2]: $$\left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$
가우스 이차상호 법칙에 의해 $$ \begin{align*} \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) =& (-1)^{ { {p-1} \over {2} }{ {3-1} \over {2} } } \\ =& (-1)^{ {{ (6k + 1) - 1 } \over {2}} } \\ =& (-1)^{3k} \\ =& (-1)^{k} \end{align*} $$
Part 1-2. 오일러 판정법
오일러 판정법: $$a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}$$
오일러 판정법에 의해 $$ \left( {{-1} \over {p}} \right) \equiv (-1)^{ {{ p - 1 } \over {2}} } \equiv (-1)^{k} \pmod{p} $$
Part 1-3. 르장드르 기호의 곱셈적 성질
르장드르 기호의 곱셈적 성질: $2$ 보다 큰 소수 $p$ 에 대해, $$\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$$
르장드르 기호의 곱셈적 성질에 의해 $$ \left( { { 3 } \over { p } } \right) = \left( { { -1 } \over { p } } \right) \left( { { -3 } \over { p } } \right) $$ $p \equiv 1 \pmod{3}$ 이므로 $x^2 \equiv p \pmod{3 }$ 을 만족하는 $x=1$ 이 존재해서 $$ \left( { { p } \over { 3 } } \right) = 1 $$ 이어야한다. 따라서 다음을 얻는다. $$ \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = \left( { { -1 } \over { p } } \right) \left( { { -3 } \over { p } } \right) $$
Part 1-4.
- Case 1. $k$ 가 짝수
- Part 1-1에 의해 $\displaystyle \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = 1$
- Part 1-2에 의해 $\displaystyle \left( { { -1 } \over { p } } \right) = 1$
- Part 1-3에 의해 $\displaystyle 1 = 1 \cdot \left( { { -3 } \over { p } } \right)$
- Case 2. $k$ 가 홀수
- Part 1-1에 의해 $\left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = -1$ 이므로 $\displaystyle \left( { { p } \over { 3 } } \right) = - \left( { { 3 } \over { p } } \right)$
- Part 1-2에 의해 $\left( { { -1 } \over { p } } \right) = -1$ 이므로 $\displaystyle \left( { { p } \over { 3 } } \right) = \left( { { -1 } \over { p } } \right) \left( { { 3 } \over { p } } \right) = \left( { { -3 } \over { p } } \right)$
- Part 1-3에 의해 $\displaystyle 1 = \left( { { -3 } \over { p } } \right)$
어떤 경우든 $-3$ 은 $p$ 에서 이차잉여고, $c^{2} \equiv -3 \pmod{p}$ 를 만족하는 $c \in \mathbb{Z}$ 가 존재한다. 양변에 $B^2$ 을 곱하고 이항하면 $$ (cB)^2 + 3 B^2 \equiv 0 \pmod{ p } $$ 이고, $A := (cB)$ 이라 두면 어떤 $M \in \mathbb{Z}$ 에 대해 $$ A^2 + 3 B^2 = Mp $$ 이다. 또한 $$ M = {{ A^2 + 3 B^2 } \over {p}} \le {{ (p-1)^2 - 3 \cdot 1^2 } \over {p}} = p - {{ 2p - 4 } \over {p}} < p $$ 이므로 $M < p$ 이다. 이 $M$ 을 계속 줄여서 $M=1$ 이 되면 어떤 $a,b \in \mathbb{Z}$ 에 대해 $p = a^2 + 3 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 + 3B^2 = pM$ 이었으므로 $$ u^2 + 3 v^2 \equiv A^2 + 3 B^2 \equiv 0 \pmod{M} $$ 이고, 어떤 $r \in \mathbb{Z}$ 에 대해 $u^2 + 3 v^2 = rM$ 이다.
Part 2-1. $r < M$
$$ r = {{ u^2 + 3 v^2 } \over {M}} \le {{ (M/2)^2 + 3 (M/2)^2 } \over { M }} \le M $$ 이므로 $r \le M$ 이다.
$M = r$ 인 경우는 $\displaystyle {{M} \over {2}} = \left| u \right| = \left| v \right| $ 인 경우 뿐이므로 $$ u^2 + 3 v^2 = 4u^2 = 4 v^2 = M^2 $$ 이다.
- 여기서 $M = | 2u |$ 은 짝수인데, 어떤 $\alpha \in \mathbb{Z}$ 에 대해 $u = M \alpha + A = 2 |u| \alpha +A$ 이므로 $u \equiv A \pmod{ 2 } $ 이다.
- 마찬가지로 $M = | 2v |$ 이고, 어떤 $ \beta \in \mathbb{Z}$ 에 대해 $v = M \beta + B = 2 |v| \beta +B$ 이므로 $v \equiv B \pmod{ 2 } $ 이다.
정리하면 $u$ 와 $A$ 는 동시에 홀수거나 짝수여야하고, $v$ 와 $B$ 도 동시에 홀수거나 짝수여야한다. 이에 대해 $$ A^2 + 3 B^2 = Mp = 2 |u| p $$ 라는 식이 성립가능한지 확인해보자.
- Case 1. $A$ 와 $B$ 가 모두 짝수
$A$ 가 짝수이므로, $|u|$ 역시 짝수가 되어 $2$ 로 나눌 수 있다. $A^2 + 3 B^2 = 2 |u| p$ 의 양변을 $4$ 로 나누면 $$ \left( {{A} \over {2}} \right) ^2 + 3 \left( {{B} \over {2}} \right) ^2 = \left( {{ | u | } \over {2}} \right) p $$ 이것은 Part 1에서 $A,B,M$ 을 지나치게 크게 잡은 것이다. 새로운 $$ A ' := \left( {{A} \over {2}} \right) \\ B ' := \left( {{B} \over {2}} \right) \\ M’ := \left( {{ |u| } \over {2}} \right) $$ 를 잡고 Part 2를 다시 시작하면 된다. - Case 2. $A$ 는 짝수, $B$ 는 홀수
$A^2 + 3 B^2 = 2 |u| p$ 의 좌변은 홀수인데 우변은 짝수이므로 식 $A^2 + 3 B^2 = Mp$ 는 성립하지 않는다. - Case 3. $A$ 는 홀수, $B$ 는 짝수
$A^2 + 3 B^2 = 2 |u| p$ 의 좌변은 홀수인데 우변은 짝수이므로 식 $A^2 + 3 B^2 = Mp$ 는 성립하지 않는다. - Case 4. $A$ 와 $B$ 가 모두 홀수 어떤 $n,m \in \mathbb{Z}$ 에 대해 $A := 2n + 1$, $B := 2m +1$ 이라고두자. $$ A^2 + 3 B^3 = 4n^2 + 4n + 1 + 3( 4 m^2 + 4m + 1 ) = 4( n^2 + n + 3 m^2 + 3m + 1) $$ 는 $4$ 의 배수다. 그러나 $| u |$ 와 $p$ 는 홀수이므로, $Mp = 2 | u | p$ 는 $4$ 의 배수가 될 수 없고 식 $A^2 + 3 B^2 = Mp$ 는 성립하지 않는다.
가능한 모든 경우를 검토해보면 Case 2~4에 의해 $r < M$ 임을 알 수 있다.
Part 2-2. $1 \le r$
$r = 0$ 이라고 가정하면 $\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$ 이므로 $A, B$ 는 $M$ 의 배수고 $A^2 + 3 B^2$ 는 $M^2$ 의 배수여야한다. 즉 $M$ 이 $p$ 의 배수여야하는데 Part 1에서 $M < p$ 임을 보였으므로 이는 불가능하다. 따라서 $r$ 은 $0$ 보다는 커야한다.
Part 2-1과 Part 2-2를 취합하면 $1 \le r < M$ 을 얻는다.
Part 3. 변형된 코시-슈바르츠 등식
$$ \begin{align*} & (u^2 + 3 v^2) ( A^2 + 3 B^2 ) \\ = & u^2 A^2 + 3 v^2 A^2 + 3 u^2 B^2 + 9 v^2 B^2 \\ = & ( u^2 A^2 + 6uAvB + 3v^2 B^2 ) + ( 3 v^2 A^2 - 6uAvB + 3 u^2 B^2 ) \\ = & ( uA + 3 vB )^2 + 3 ( uA - vB )^2 \end{align*} $$ 한편 $$ 3 ( uA - vB ) \equiv 3 ( BA - AB ) \equiv 0 \pmod{M} $$ 이므로 $3 ( uA - vB )$ 은 $M$ 의 배수다. Part 2에서 $$ ( uA + 3 vB ) \equiv AA + 3 BB \equiv 0 \pmod{M} $$ 이므로 $( uA + 3 vB )$ 은 $M$ 의 배수다.
Part 4.
$A^2 + 3 B^2 = Mp$ 이고 $u^2 + 3 v^2 = Mr$ 이므로 $$ (u^2 + 3 v^2) ( A^2 + 3 B^2 ) = M^2 r p $$ 변형된 코시-슈바르츠 등식을 이용하면 $$ ( uA + 3 vB )^2 + 3 ( uA - vB )^2 = M^2 r p $$ 위의 Part 3에서 $( uA + 3 vB )$ 와 $3 ( uA - vB )$ 은 $M$ 의 배수이므로 양변을 $M^2$ 으로 나누면 $$ \left( {{ uA + 3 vB } \over {M}} \right)^2 + 3 \left( {{ uA - vB } \over {M}} \right)^2 = r p $$
이에 대해 새로운 $$ A_{2} : = \left( {{ uA + 3 vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r $$ 을 정의하면, 다시 $A_{2}^{2} + 3 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 - ab + b^2$ 만족하는 $a,b$ 를 $3$ 으로 나눈 몫이 $n,m$ 이라고 하자.
- $N_{0} = 3k + 0$ 이면 $$ N_{0}^{2} \equiv 9k^2 \equiv 0 \pmod{ 3 } $$
- $N_{1} = 3k + 1$ 이면 $$ N_{1}^{2} \equiv \left( 9k^2 + 6k \right) + 1 \equiv 1 \pmod{ 3 } $$
- $N_{2} = 3k + 2$ 이면 $$ N_{0}^{2} \equiv \left( 9k^2 + 12k + 3 \right) + 1 \equiv 1 \pmod{ 3 } $$
따라서 $\pmod{3}$ 에서 $3$ 의 배수가 아닌 자연수 $N$ 에 대해서는 하여튼 $N^2 \equiv 1 \pmod{ 3 }$ 이다.
이제부터 $a$, $b$ 가 나올 수 있는 모든 조합을 생각해보자.
- Case 00. $a= 3n$, $b = 3m$ $$ p = 9 n^2 - 9 nm + 9 m^2 = 3 ( 3 n^2 - 3 nm + 3 m^2) $$ 소수 $p$ 가 $3$ 의 배수가 되므로 이러한 조합은 불가능하다.
- Case 01. $a= 3n$, $b = 3m + 1$ $$p \equiv 9 n^2 - 3n b + b^2 \equiv 1 \pmod{ 3 }$$
- Case 02. $a= 3n$, $b = 3m + 2$ $$p \equiv 9 n^2 - 3n b + b^2 \equiv 1 \pmod{ 3 }$$
- Case 11. $a= 3n + 1$, $b = 3m + 1$ $$p \equiv a^2 - ( 3n + 1 ) ( 3m + 1) + b^2 \equiv 1 - 9nm - 3n - 3m - 1 + 1 \equiv 1 \pmod{3}$$
- Case 12. $a= 3n + 1$, $b = 3m + 2$ $$ \begin{align*} p =& (3n+1)^2 - ( 3n + 1 ) ( 3m + 2 ) + (3m+2)^2 \\ =& 9n^2 + 6n + 1 - 9nm - 6n - 3m - 2 + 9m^2 + 12m + 4 \\ =& 3 ( 3n^2 + 3m^2 - 3nm + 2n + 4m + 1 ) \end{align*} $$ 소수 $p$ 가 $3$ 의 배수가 되므로 이러한 조합은 불가능하다.
- Case 22. $a= 3n + 2$, $b = 3m + 2$ $$ \begin{align*} p \equiv& a^2 - ( 3n + 2 ) ( 3m + 2 ) + n^2 \\ \equiv& 1 - 9nm - 6n - 6m - 4 + 1 \\ \equiv& -2 \\ \equiv& 1 \pmod{3} \end{align*} $$ 모든 경우를 살펴보면 Case 01, Case 02, Case 11, Case 22와 같은 경우엔 $p \equiv 1 \pmod{3}$ 이고, Case 00, Case 12와 같은 경우는 일어나지 않는다.
■