소수를 3으로 나눈 나머지가 1이 되는 필요충분조건

소수를 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 $$

이러한 팩트는 그 자체만으로도 흥미롭지만, 아이젠슈타인 정수와 깊은 연관이 있어 정수론을 한 차원 높은 곳으로 이끈다.

증명

$( \Rightarrow ) $

$$ 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.

어떤 경우든 $-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 $$ 이다.

정리하면 $u$ 와 $A$ 는 동시에 홀수거나 짝수여야하고, $v$ 와 $B$ 도 동시에 홀수거나 짝수여야한다. 이에 대해 $$ A^2 + 3 B^2 = Mp = 2 |u| p $$ 라는 식이 성립가능한지 확인해보자.

가능한 모든 경우를 검토해보면 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$ 으로 나누면 $$ \displaystyle \left( {{ uA + 3 vB } \over {M}} \right)^2 + 3 \left( {{ uA - vB } \over {M}} \right)^2 = r p $$

이에 대해 새로운 $$ \displaystyle 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$ 에서 멈춘다.


$( \Leftarrow ) $

$p=a^2 - ab + b^2$ 만족하는 $a,b$ 를 $3$ 으로 나눈 몫이 $n,m$ 이라고 하자.

따라서 $\pmod{3}$ 에서 $3$ 의 배수가 아닌 자연수 $N$ 에 대해서는 하여튼 $N^2 \equiv 1 \pmod{ 3 }$ 이다.

이제부터 $a$, $b$ 가 나올 수 있는 모든 조합을 생각해보자.

같이보기

댓글