AOPS 직접 풀이 #002

문제 링크

스포 방지를 위해 더보기 기능을 쓰니까 수식이 깨지는 문제가 있어서 그냥 밑으로 내리기로 했다.

statement : 

$\omega := \omega^p = 1$의 한 허근

$$X := \sum_{\text{k : Quadratic Residue of mod }p}\omega^{k}$$

$$Y := \sum_{\text{k : Quadratic Irresidue of mod }p}\omega^{k}$$

$XY \in \mathbb{Z}$임을 보여라.

---

이차잉여 개념을 이용해서 해결할 수 있는데, 수업 시간에 배우기도 했던 중요한 Lemma를 사용할 수 있다.

일단 $X,Y$가 굉장히 보기 싫으니까 이렇게 바꾸자.

$$X = \frac{1}{2}\sum_{k=1}^{p-1}(1+(\frac{k}{p})) \omega^k$$,

$$Y = \frac{1}{2}\sum_{k=1}^{p-1}(1-(\frac{k}{p})) \omega^k$$

그렇다면 $XY$는 다음과 같다.

$$4XY = \sum_{i=1}^{p-1}\sum_{j=1}^{p-1} \left(1 + (\frac{i}{p}) - (\frac{j}{p}) - (\frac{ij}{p})\right) \omega^{i+j} \\ = \sum_{k=1}^{p-1} \left[ \sum_{i=1}^{p-1} \left( 1 + \color{red}{(\frac{i}{p})}-\color{blue}{(\frac{k-i}{p})} - (\frac{i(k-i)}{p})\right) \right] \omega^k$$

빨간색, 파란색 항은 다 더하면 소거되니까,

$$4XY = \sum_{k=1}^{p-1} \left( p-1 - \sum_{i=1}^{p-1}(\frac{-i^2 + ki}{p}) \right) \omega^k$$

■Lemma

이 때, 이차식 $f(x) = ax^2 + bx + c$에 대해

$$\sum_{x=0}^{p-1} (\frac{f(x)}{p}) = \begin{cases} -(\frac{a}{p}) 
& (p \not{|} b^2 - 4ac) \\ (p-1)(\frac{a}{p}) & (p \ | \ b^2 - 4ac) \end{cases} $$

여기서 판별식 $D = k^2 \not{\equiv} 0 (\text{mod }p)$이므로,

$$4XY = \sum_{k=1}^{p-1} \left(p - 1 - (\frac{-1}{p})\right) \omega^k = -p + 1 + (\frac{-1}{p})$$

따라서 $XY = \frac{-p + 1+ (\frac{-1}{p})}{4}$가 성립하고, 이 값은 정수가 됨을 쉽게 증명할 수 있다. $\blacksquare$