$x^2+xy+y^2$꼴 자연수

우리가 어떤 자연수 $n$이 주어져 있고 이 $n$이 $x^{2}+xy+y^{2}(x,y\in\mathbb{Z})$로 나타내질 수 있는지 알고싶다. 그러기 위해서는 먼저 어떤 소수 $p$가 $x^{2}+xy+y^{2}$인지 알아보자. 

 

Lemma 1. 소수 $p$에 대하여 $p=x^{2}+xy+y^{2}(x,y\in\mathbb{Z})$ iff $p\equiv 1\pmod{3}$거나 $p=3$이다. 

(pf) $(\Rightarrow)$ $x$가 3의 배수라고 가정하자. 만약 $3|y$이면 $p$가 소수라는 가정에 모순이다. 따라서 $3\nmid y$이고 $p\equiv 1\pmod{3}$이다. $x,y$가 3의 배수가 아니라고 가정하자. 그럼 $x,y$는 3으로 나눈 나머지가 $1,2$중 하나가 될 것이다. 만약 $x\not\equiv y\pmod{3}$이면 $p\equiv 1\pmod{3}$이 된다. 만약 $x\equiv y\pmod{3}$이면 $3|p$이며 $p=3$이 된다. $(\Leftarrow)$ 우리가 정수 $x$에 대한 이차방정식 $x^{2}+xy+(y^{2}-p)=0$을 푼다고 가정하자. 판별식 $D$의 값은 제곱수 $m^{2}$가 되어야한다. 그럼 $y^{2}-4(y^{2}-p)=m^{2}$이며 $4p=m^{2}+3y^{2}$이다. 우리는 다음과 같은 간단한 항등식을 통해 $p=a^{2}+3b^{2}$임을 보이기만 하면 된다는 것을 알 수 있다. ($4=1^{2}+3\cdot 1^{2}$)

$$(a^{2}+3b^{2})(c^{2}+3d^{2})=(ac-3bd)^{2}+3(ad+bc)^{2}$$

합동방정식 $x^{2}\equiv -3\pmod{p}$의 해는 주어진 조건에서 존재함을 쉽게 알 수 있다. Thue의 정리에 의해서 $ax\equiv b\pmod{p}$인 $0\le |a|,|b|<\sqrt{p}$가 존재한다. 이를 제곱하면, $kp=3a^{2}+b^{2}<4p$이다. 가능한 $k$는 $1,2,3$이다. $k=3$인 경우, $3|b$이며 $b=3b'$이면 $p=a^{2}+3b'^{2}$이다. $k=2$인 경우, $a,b$는 둘 다 짝수거나 홀수이다. 둘 다 짝수인 경우 $4|p$이므로 모순이다. $a=2n+1,b=2m+1$을 가정하면, $2p=3(4n^{2}+4n+1)+(4m^{2}+4m+1)$이고 $p=3(2n^{2}+2n)+2(m^{2}+m+1)$이 된다. $p\equiv 1\pmod{3}$인 경우, $m^{2}+m+1\equiv 2\pmod{3}$이어야 하며 이를 만족하는 $m$이 존재하지 않는다. $p=3$인 경우 $m^{2}+m+1\equiv 0 \pmod{3}$이어야 하며 이를 만족하는 $m$ 역시 존재하지 않는다. 따라서, $p=a^{2}+3b^{2}$의 꼴로 항상 표현 가능함을 알 수 있다. 그럼 $4p=(a^{2}+3b^{2})(1^{2}+3\cdot 1^{2})=(a-3b)^{2}+3(a+b)^{2}$이고 $a+b=y$이며 $m=a-3b$이고, $x=\frac{-(a+b)\pm(a-3b)}{2}=-2b,-a+b$임을 확인할 수 있다. $\blacksquare$

 

Ex) $p=13$

$x^{2}\equiv -3\pmod{13}$의 해는 $x=7$이다. $2\cdot 7\equiv 1\pmod{13}$이며 $2,1<\sqrt{13}$이다. 따라서 $13=1^{2}+3\cdot 2^{2}$이다. Lemma 1에 의해 $x=-4, y=3$이라 설정하면 $(-4)^{2}+3\cdot (-4)+3^{2}=13$임을 확인할 수 있다.

 

Lemma 2. 어떤 정수 $n$이 정수 $x,y$에 대해서 $n=x^{2}+xy+y^{2}$을 만족하면 어떤 자연수 $k,m$에 대하여 $n=m^{2}p_{1}\cdots p_{k}$이고 각 $p_{i}$는 $p_{i}\equiv 1\pmod{1}$인 소수이다. 

(pf) $\alpha:=\frac{1+\sqrt{-3}}{2}$라 두자. 그럼 $p|(x+\alpha y)(x+\overline{\alpha}y)$ in $\mathbb{Z}[\alpha]$이다. 만약 $p$가 $p|x+\alpha y, x+\overline{\alpha} y$라면, $x,y$는 $p$의 배수가 되어야한다. 즉, $p^{2}|n$이다. 만약 소수 $p$가 $(x+\alpha y),(x+\overline{\alpha}y)$를 나누지 않는다면 $p$는 $\mathbb{Z}[\alpha]$에서 소수가 아니다. $\mathbb{Z}[\alpha]$가 UFD이므로 $p=\pi_{1}\cdots \pi_{n}$이 $p$의 $\mathbb{Z}[\alpha]$에서의 소인수분해라고 하자. 그럼 $p^{2}=N(p)=N(\pi_{1})\cdots N(\pi_{n})$이며 정수에서의 소인수분해의 유일성에 의해 $n\le 2$이다. $n=1$이면 $p$는 $\mathbb{Z}[\alpha]$에서 소수이므로 모순이며 $n=2$인 경우 $N(\pi_{1})=N(\pi_{2})=p$이다. $\pi_{1}=a+\alpha b$라고 두면 $N(\pi_{1})=a^{2}+ab+b^{2}=p$가 된다. $\blacksquare$