이차잉여
개요
- 정수 $a$를 소수 $p$로 나눈 나머지가 어떤 완전제곱수를 $p$로 나눈 나머지와 같으면 $p$에 대한 이차잉여라 한다
- 소수 $p$에 대하여, 이차합동식 \(x^2\equiv a \pmod p\) 의 해의 개수에 관련된 문제로 볼 수 있다
- 두 홀수인 소수 $p,q$가 서로의 법에 대한 이차잉여가 될 조건은 긴밀히 연관되어 있으며, 이를 이차잉여의 상호법칙이라 한다
이차잉여
예
- 합동식 (모듈로 modulo 연산)
- 소수 3에 대한 이차잉여
- 3으로 나눈 나머지가 1인수
- 소수 5에 대한 이차잉여
- 5로 나눈 나머지가 1 또는 4
- 이차잉여를 판정하는 하나의 방법은 가우스의 보조정리(Gauss's lemma)를 사용하는 것이다
군을 통한 이해
- 소수 $p$에 대하여, \((\mathbb{Z}/p\mathbb{Z})^\times\)는 순환군이다
- 순환군으로서의 생성원은 소수에 대한 원시근(primitive root) 목록 항목 참조
- 이차잉여가 이루는 \((\mathbb{Z}/p\mathbb{Z})^\times\)의 부분집합은 곱셈에 대한 부분군이 된다
테이블
- 처음 몇개의 소수에 대한 이차잉여와 비이차잉여
$$ \begin{array}{c|c|c} \text{} & \text{quadratic residue} & \text{quadratic non-residue} \\ \hline 2 & \{1\} & \{\} \\ 3 & \{1\} & \{2\} \\ 5 & \{1,4\} & \{2,3\} \\ 7 & \{1,2,4\} & \{3,5,6\} \\ 11 & \{1,3,4,5,9\} & \{2,6,7,8,10\} \\ 13 & \{1,3,4,9,10,12\} & \{2,5,6,7,8,11\} \\ 17 & \{1,2,4,8,9,13,15,16\} & \{3,5,6,7,10,11,12,14\} \\ 19 & \{1,4,5,6,7,9,11,16,17\} & \{2,3,8,10,12,13,14,15,18\} \\ 23 & \{1,2,3,4,6,8,9,12,13,16,18\} & \{5,7,10,11,14,15,17,19,20,21,22\} \\ 29 & \{1,4,5,6,7,9,13,16,20,22,23,24,25,28\} & \{2,3,8,10,11,12,14,15,17,18,19,21,26,27\} \end{array} $$
가우스 합
- $A,B$를 다음과 같이 정의하자
\[A=\sum_{a\in QR} \zeta^a,\quad B=\sum_{a\in QNR} \zeta^a\] 다음이 성립한다 \[A+B=-1\] \[A-B=\sum_{a=1}^{p-1} \left(\frac{a}{p}\right) \zeta^a\]
- $A-B$는 가우스 합 $G(p)=\sum_{r=0}^{p-1} e^{2\pi i r^2/p}$
디리클레 유수 공식의 응용
- 7 이상의 소수 \(p \equiv 3 \pmod{4}\)를 생각하자
- 이차수체 \(K=\mathbb{Q}(\sqrt{-p})\) 라 두면, \(d_K=-p\)
- 준동형사상 $\chi \colon(\mathbb{Z}/d_K\mathbb{Z})^\times \to \mathbb C^{\times}$, \(\chi(a)=\left(\frac{a}{p}\right)\) 를 정의하자.
- \(p \equiv 3 \pmod{4}\) 이므로 \(\chi(-1)=-1\)이고, 디리클레 L-함수에서 다음을 얻는다
\[L(1,\chi)=\frac{i\pi \tau(\chi)}{p}\sum_{a=1}^{p-1}\bar\chi(a)\frac{a}{p}=\frac{i\pi \tau(\chi)}{p}\sum_{a=1}^{p-1}\chi(a)\frac{a}{p}\]
- 한편, 이차 수체에 대한 디리클레 유수 (class number) 공식에서 다음을 얻는다
\[L(1,\chi)=\frac{\pi h_K}{\sqrt p}\]
- 가우스 합은 \(\tau (\chi)=i\sqrt p\) 이므로 위의 두 값을 비교하면,
\[h_K=\frac{\sqrt p }{\pi}\frac{i\pi\tau(\chi)}{p}\sum_{a=1}^{p-1}\chi(a)\frac{a}{p}=-\sum_{a=1}^{p-1}(\frac{a}{p})\frac{a}{p}\]
- $p=3$이면 $-\sum_{a=1}^{p-1}(\frac{a}{p})a=-1+2=1$
- 이로부터 소수 \(p \equiv 3 \pmod{4}\)에 대하여 기약잉여계 $\{1,2,\cdots, p-1\}$에서의 이차비잉여의 합이 이차잉여의 합보다 크다는 것을 알 수 있다.
- $p \equiv 1 \pmod{4}$이면, 다음이 성립한다
$$ \sum_{a=1}^{p-1}(\frac{a}{p})a=0 $$
관련된 항목들
매스매티카 파일 및 계산 리소스
관련논문
- http://arxiv.org/abs/1512.00896
- Tao, Terence. ‘The Elliott-Halberstam Conjecture Implies the Vinogradov Least Quadratic Nonresidue Conjecture’. arXiv:1410.7073 [math], 26 October 2014. http://arxiv.org/abs/1410.7073.