이차 상호 법칙

수론에서 **이차 상호 법칙**(二次相互法則, law of quadratic reciprocity)은 두 홀수 소수가 서로에 대하여 제곱잉여인지 여부가 대칭적이라는 정리다.
# 정의
**이차 상호 법칙**에 따르면, p와 q가 서로 다른 홀수 소수일 때, 이차 합동식 :\begin{cases}x^2 \equiv p \pmod q \\\ y^2 \equiv q \pmod p \end{cases} 에 대하여 다음 두 경우가 성립한다. * 만약 p\equiv q\equiv3\pmod4라면 두 합동식 가운데 하나는 해가 존재하고, 다른 하나는 해가 존재하지 않는다. * 그밖의 경우 둘 다 해가 존재하든지 둘 다 해가 존재하지 않는다. 서로 다른 두 홀수 소수 p와 q에 대하여 르장드르 기호 \left(\frac{p}{q}\right)는 p가 q에 대한 제곱잉여일 때 1, 그렇지 않을 때 -1로 정의된다. 르장드르 기호를 이용하면, **이차 상호 법칙**을 다음과 같이 간단히 나타낼 수 있다. :\left(\frac pq\right) \left(\frac qp\right) = (-1)^{(p-1)(q-1)/4} 우변은 p와 q를 4로 나눈 나머지가 둘 다 3일 때만 -1이 된다. 위의 등식은 야코비 기호로 확장할 수 있다. 1이 아닌 두 홀수 m과 n이 서로소일 때, :\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) = (-1)^{(m-1)(n-1)/4} 이 성립한다. 또한, p>2가 소수라면 다음 두 법칙이 성립한다. :\left(\frac{-1}p\right)=(-1)^{(p-1)/2} :\left(\frac2p\right)=(-1)^{(p^2-1)/8} 이를 각각 **이차 상호 법칙의 제1 보충**(二次相互法則의第一補充, first supplement to quadratic reciprocity)과 **이차 상호 법칙의 제2 보충**(二次相互法則의第二補充,second supplement to quadratic reciprocity)이라고 한다.
## 가우스 정수의 이차 상호 법칙
가우스 정수의 경우, 다음과 같은 형태의 이차 상호 법칙이 성립한다. p\in\mathbb Z[i]가 2가 아닌 가우스 소수이며, k\in\mathbb Z[i]가 p의 배수가 아닌 가우스 정수라고 하자. 그렇다면 르장드르 기호와 유사하게 다음 기호를 정의하자. :\left[\frac kp\right]_2=\begin{cases}+1&p;\nmid k\land \exists n\in\mathbb Z[i]\colon n^2\equiv k\pmod p\\\ -1 &p;\nmid k\land \nexists n\in\mathbb Z[i]\colon n^2\equiv k\pmod p \\\ 0&p;\mid k \end{cases} 그렇다면 다음이 성립한다. :\left[\frac kp\right]_2\equiv k^{(N_{\mathbb Q[i]/\mathbb Q}(p) - 1)/2}\pmod p 여기서 :N_{\mathbb Q[i]/\mathbb Q}\colon a+bi\mapsto a^2+b^2 는 가우스 정수의 체 노름이다. 서로 다른 두 가우스 소수 p,q\in\mathbb Z[i]에 대하여, :\operatorname{Re} p\equiv\operatorname{Re}q\equiv1\pmod2 :\operatorname{Im} p\equiv\operatorname{Im} q\equiv0\pmod2 라고 하자. 그렇다면 다음이 성립한다. :\left[\frac pq\right]_2 = \left[\frac qp\right]_2 또한, i 및 1+i에 대하여 다음이 성립한다. :\left[\frac{i}{p}\right]_2 =(-1)^{\operatorname{Im} p/2} :\left[\frac{1+i}p\right]_2 =\Bigg(\frac{2}{\operatorname{Re}p+\operatorname{Im}p}\Bigg)
## 아이젠슈타인 정수의 이차 상호 법칙
아이젠슈타인 정수의 경우, 다음과 같은 형태의 이차 상호 법칙이 성립한다. p\in\mathbb Z[\omega]가 아이젠슈타인 소수이며, N(p)\ne3이라고 하자. 또한, k\in\mathbb Z[\omega]가 p의 배수가 아닌 아이젠슈타인 정수라고 하자. 그렇다면 르장드르 기호와 유사하게 다음 기호를 정의하자. :\left[\frac kp\right]_2=\begin{cases}+1&\exists n\in\mathbb Z[\omega]\colon n^2\equiv k\pmod p\\\ -1 &\nexists n\in\mathbb Z[\omega]\colon n^2\equiv k\pmod p \end{cases} 그렇다면 다음이 성립한다. :\left[\frac kp\right]_2\equiv k^{(N(p) - 1)/2}\pmod p 여기서 :N\colon a+b\omega\mapsto a^2-ab+b^2=(a+b\omega)(a+b\bar\omega) 는 아이젠슈타인 정수의 체 노름이다. 서로 다른 두 아이젠슈타인 소수 p,q\in\mathbb Z[\omega]가 :p=a+b\omega\qquad(3\nmid a,\;3\mid b) :q=c+d\omega\qquad(3\nmid c,\;3\mid d) 의 꼴이라고 하자. 그렇다면 다음이 성립한다. :\left[\frac pq\right]_2 \left[\frac qp\right]_2=(-1)^{(N(p)-1)(N(q)-1)/4)} 또한, 다음이 성립한다. :\left[\frac{1-\omega}{p}\right]_2 =\left(\frac a3\right) :\left[\frac2p\right]_2 =\left(\frac{2}{N(p)}\right)
# 역사
이차 상호 법칙을 다루고 있는 《산술 연구》의 쪽 레온하르트 오일러와 아드리앵마리 르장드르는 이차 상호 법칙을 추측하였으나 증명하지 못했다. 카를 프리드리히 가우스가 《산술 연구》(디스퀴시티오네스 아리트메티카이)에서 최초로 이차 상호 법칙을 증명하였다. 가우스는 이차 상호 법칙을 "기본 정리"(테오레마 푼다멘탈레)라고 불렀고, 이에 대하여 다음과 같이 적었다. 장=151. De aliorum laboribus circa has investigationes 가우스는 평생에 걸쳐 이차 상호 법칙의 8가지 다른 증명을 제시하였다. 가우스 이후, 현재까지 발표된 이차 상호 법칙의 증명들은 200여 개에 이르며, 최근까지도 꾸준히 새로운 증명들이 발표되고 있다.언어=en
# 예
두 홀수 소수들 사이의 제곱 잉여 여부를 표로 나타내면 다음과 같다. 이차 상호 법칙에 따라, 표가 대각선을 중심으로 대칭이거나 반대칭임을 알 수 있다. {| class="wikitable" |+ 범례 |- |width="25" |**R** | align="left" | *q*는 제곱잉여 (mod *p*) |rowspan="2" | *q* ≡ 1 (mod 4) 또는 *p* ≡ 1 (mod 4) |- |width="25" |**N** || align="left" | *q*는 제곱잉여가 아님 (mod *p*) |- |width="25" |**R** | align="left" | *q*는 제곱잉여 (mod *p*) | rowspan="2" | *q* ≡ *p* ≡ 3 (mod 4) |- |width="25" |**N** || align="left" | *q*는 제곱잉여가 아님 (mod *p*) |} {| class="wikitable" |- | colspan="2" rowspan="2" | ! colspan="24" | *q* |- !width="25" | 3 !width="25" | 5 !width="25" | 7 !width="25" |11 !width="25" |13 !width="25" |17 !width="25" |19 !width="25" |23 !width="25" |29 !width="25" |31 !width="25" |37 !width="25" |41 !width="25" |43 !width="25" |47 !width="25" |53 !width="25" |59 !width="25" |61 !width="25" |67 !width="25" |71 !width="25" |73 !width="25" |79 !width="25" |83 !width="25" |89 !width="25" |97 |- !rowspan="24" width="25" | *p* ! width="25" | 3 ! ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** |- ! 5 ||**N** ! ||**N** ||**R** ||**N** ||**N** ||**R** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** |- !7 ||**N** ||**N** ! ||**R** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** |- ! 11 ||**R** ||**R** ||**N** ! ||**N** ||**N** ||**N** ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**R** ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**R** ||**R** |- ! 13 ||**R** ||**N** ||**N** ||**N** ! ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**R** ||**N** ||**N** ||**N** |- !17 ||**N** ||**N** ||**N** ||**N** ||**R** ! ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** |- !19 ||**N** ||**R** ||**R** ||**R** ||**N** ||**R** ! ||**R** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** |- !23 ||**R** ||**N** ||**N** ||**N** ||**R** ||**N** ||**N** ! ||**R** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**N** |- !29 ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ! ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**N** ||**N** |- !31 ||**N** ||**R** !|**R** ||**N** ||**N** ||**N** ||**R** ||**N** ||**N** ! ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**N** ||**R** |- !37 ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**N** ! ||**R** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** |- !41 ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**N** ||**R** ||**R** ! ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** |- !43 ||**N** ||**N** ||**N** ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ! ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** |- !47 ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**R** ||**N** ||**N** ! ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**R** ||**R** ||**R** ||**R** |- !53 ||**N** ||**N** ||**R** ||**R** ||**R** ||**R** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**R** ! ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** |- !59 ||**R** ||**R** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**N** ||**N** ||**R** ! ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** |- !61 ||**R** ||**R** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ! ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** |- !67 ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ! ||**R** ||**R** ||**N** ||**R** ||**R** ||**N** |- !71 ||**R** ||**R** ||**N** ||**N** ||**N** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ! ||**R** ||**R** ||**R** ||**R** ||**N** |- !73 ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**R** ! ||**R** ||**N** ||**R** ||**R** |- !79 ||**N** ||**R** ||**N** ||**R** ||**R** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**N** ||**R** ! ||**R** ||**R** ||**R** |- !83 ||**R** ||**N** ||**R** ||**R** ||**N** ||**R** ||**N** ||**R** ||**R** ||**R** ||**R** ||**R** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**N** ||**N** ! ||**N** ||**N** |- !89 ||**N** ||**R** ||**N** ||**R** ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**R** ||**N** ||**N** ||**R** ||**R** ||**R** ||**R** ||**N** ! ||**R** |- !97 ||**R** ||**N** ||**N** ||**R** ||**N** ||**N** ||**N** ||**N** ||**N** ||**R** ||**N** ||**N** ||**R** ||**R** ||**R** ||**N** ||**R** ||**N** ||**N** ||**R** ||**R** ||**N** ||**R** ! |} 제곱 잉여 문제의 일부 예는 다음과 같다. {| class="wikitable" |- ! (*p*, *q*) !! p\stackrel{?}{\equiv} 3\stackrel{?}{\equiv} q\pmod 4 || x^2\equiv p\pmod q || x^2\equiv q\pmod p |- | (3,7) || p \equiv3\equiv q \pmod4 || 해 없음 || y\equiv\pm1\pmod3 |- | (3,5) || p \equiv 3\not\equiv q \pmod4 || 해 없음 || 해 없음 |- | (5,11) || p \not\equiv 3\equiv q \pmod4 || x\equiv\pm4\pmod{11} || y\equiv\pm1\pmod5 |- | (5, 13) || p \not\equiv 3\not\equiv q \pmod4 || 해 없음 || 해 없음 |- | (13, 17) || p \not\equiv 3\not\equiv q \pmod4 || x\equiv\pm8\pmod{17} || y\equiv\pm2\pmod{13} |}
## 제곱잉여의 판별
일반적으로 어떤 수가 제곱잉여인지 아닌지를 판별하는 문제는 쉽지 않다. 이때 이차상호법칙을 이용하여 문제를 해결할 수 있다. 예를 들어, 다음 합동식 :x^2 \equiv 57 \pmod{127} 이 해를 가지는지를 판별하여 보자. 이것은 르장드르 기호 \left( \frac{57}{127} \right)의 값을 구하면 된다. 르장드르 기호의 성질에 의해, :\left( \frac{57}{127} \right) = \left( \frac{3}{127} \right) \left( \frac{19}{127} \right) 이다. 한편 3, 19, 127은 모두 4로 나눈 나머지가 3인 소수이므로 이차상호법칙에 의해 :\left(\frac{3}{127}\right) =(-1)^{\frac{(3-1)(127-1)}{4\left(\frac{127}{3}\right) =(-1)\left(\frac{1}{3}\right) = -1 이고 :\left(\frac{19}{127}\right) =(-1)^{\frac{(19-1)(127-1)}{4\left(\frac{127}{19}\right) =(-1)\left(\frac{13}{19}\right) :=(-1)(-1)^{\frac{(13-1)(19-1)}{4\left(\frac{19}{13}\right) =(-1)\left(\frac{6}{13}\right)=(-1)\left(\frac{2}{13}\right)\left(\frac{3}{13}\right) :=(-1)(-1)(-1)^{\frac{(3-1)(13-1)}{4\left(\frac{13}{3}\right) =\left(\frac{1}{3}\right) =1 이다. 따라서 :\left(\frac{57}{127}\right)=-1 이므로, 57은 127에 대한 제곱잉여가 아니다.