AOPS 직접 풀이 #002

2017. 12. 21. 14:59수학 문풀/경시 (내 풀이)

문제 링크


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


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\)

'수학 문풀 > 경시 (내 풀이)' 카테고리의 다른 글

RMM11 P4  (1) 2019.04.23
180206 함수방정식 풀이  (2) 2018.02.06
AOPS 직접 풀이 #004 (미완?)  (0) 2017.12.24
AOPS 직접 풀이 #002  (0) 2017.12.21
[AOPS - 직접 풀이] #001. 더블카운팅  (0) 2016.09.05
1 2 3 4 5