이차잉여의 상호법칙

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

개요

정수 \(a\)를 소수 \(p\)로 나눈 나머지가 어떤 완전제곱수를 \(p\)로 나눈 나머지와 같으면 \(p\)에 대한 이차잉여라 한다
소수 \(p\)에 대하여, 이차합동식 \(x^2\equiv a \pmod p\) 의 해의 개수에 관련된 문제로 볼 수 있다
두 홀수인 소수 \(p,q\)가 서로의 법에 대한 이차잉여가 될 조건은 긴밀히 연관되어 있으며, 이를 이차잉여의 상호법칙이라 한다
정수론의 중심적인 주제인 정수론에서의 상호법칙 (reciprocity laws)의 시작

이차잉여

예

합동식 (모듈로 modulo 연산)
소수 3에 대한 이차잉여
- 3으로 나눈 나머지가 1인수
소수 5에 대한 이차잉여
- 5로 나눈 나머지가 1 또는 4
이차잉여를 판정하는 하나의 방법은 가우스의 보조정리(Gauss's lemma)를 사용하는 것이다

테이블

처음 몇개의 소수에 대한 이차잉여와 비이차잉여

\[ \begin{array}{c|c|c} \text{} & \text{quadratic residue} & \text{quadratic nonresidue} \\ \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\)와 홀수인 소수 \(p\) 에 대하여, 르장드르 부호를 다음과 같이 정의한다

\[\left(\frac{a}{p}\right) = \begin{cases} \;\;\,0\mbox{ if } a \equiv 0 \pmod{p} \\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, \;a\equiv x^2\pmod{p} \\-1\mbox{ if there is no such } x. \end{cases}\]

르장드르 부호와 자코비 부호 항목 참조

테이블

처음 몇 개의 소수들에 대한 르장드르 부호 \(\left(\frac{y}{x}\right)\)의 계산

\[ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} x\ddots y & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 \\ \hline 3 & & -1 & -1 & 1 & 1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 \\ \hline 5 & -1 & & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 & 1 & -1 & -1 & -1 \\ \hline 7 & 1 & -1 & & -1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & 1 & 1 \\ \hline 11 & -1 & 1 & 1 & & -1 & -1 & 1 & -1 & -1 & -1 & 1 & -1 & 1 & -1 & 1 \\ \hline 13 & 1 & -1 & -1 & -1 & & 1 & -1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & 1 \\ \hline 17 & -1 & -1 & -1 & -1 & 1 & & 1 & -1 & -1 & -1 & -1 & -1 & 1 & 1 & 1 \\ \hline 19 & 1 & 1 & -1 & -1 & -1 & 1 & & -1 & -1 & 1 & -1 & -1 & -1 & -1 & -1 \\ \hline 23 & -1 & -1 & 1 & 1 & 1 & -1 & 1 & & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ \hline 29 & -1 & 1 & 1 & -1 & 1 & -1 & -1 & 1 & & -1 & -1 & -1 & -1 & -1 & 1 \\ \hline 31 & 1 & 1 & -1 & 1 & -1 & -1 & -1 & 1 & -1 & & -1 & 1 & 1 & -1 & -1 \\ \hline 37 & 1 & -1 & 1 & 1 & -1 & -1 & -1 & -1 & -1 & -1 & & 1 & -1 & 1 & 1 \\ \hline 41 & -1 & 1 & -1 & -1 & -1 & -1 & -1 & 1 & -1 & 1 & 1 & & 1 & -1 & -1 \\ \hline 43 & 1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 & 1 & & -1 & 1 \\ \hline 47 & -1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & 1 & 1 & -1 & 1 & & 1 \\ \hline 53 & -1 & -1 & 1 & 1 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & -1 & 1 & 1 & \end{array} \]