📂정수론

소수를 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와 같은 경우는 일어나지 않는다.

■

같이보기

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