이차 상호법칙

개요 — 동기·문제의식

이차잉여에서 Euler 판정법으로 $\left(\frac ap\right)$ 를 계산할 수 있게 됐지만, $a^{(p-1)/2}\bmod p$ 를 매번 손으로 거듭제곱하는 건 $p$ 가 크면 번거롭다. 더 깊은 질문이 있다: $\left(\frac pq\right)$ 와 $\left(\frac qp\right)$ — 즉 "$p$ 가 $q$ 의 제곱인가"와 "$q$ 가 $p$ 의 제곱인가" — 사이에 어떤 관계가 있을까? 두 질문은 언뜻 전혀 다른 모듈러스에서 묻는, 서로 무관해 보이는 질문이다. 그런데 Gauss는 이 둘이 분모와 분자를 뒤집기만 해도 거의 같은 답을 준다는 것을 발견했다 — 정확한 부호 차이는 $p,q$ 가 둘 다 $4k+3$ 형일 때만 나타난다. 이 놀라운 대칭이 이차상호법칙이며, Gauss 스스로 "황금 정리(theorema aureum)"라 부르며 평생 8가지 다른 증명을 남겼다.¹ 실용적으로는 이 법칙이 임의의 Legendre 기호를 인수분해와 뒤집기의 반복만으로 — 어떤 거듭제곱 계산도 없이 — 빠르게 계산하게 해준다. 역사적으로는 이것이 정수론에서 가장 깊은 정리 중 하나로, 현대의 류체론(class field theory)·Artin 상호법칙·Langlands 프로그램이 모두 "상호법칙을 어떻게 일반화할 것인가"라는 질문의 후예다.

직관

상호법칙이 왜 그럴듯한지 보는 한 가지 방법은 격자점 세기다(Eisenstein의 증명 방식). $\left(\frac qp\right)$ 의 부호는 $\left\lfloor\frac{kq}p\right\rfloor$ ($k=1,\dots,\frac{p-1}2$) 들의 합의 홀짝성과 관련되는데, 이 합은 정확히 직사각형 $\frac p2\times\frac q2$ 안의 격자점 중 특정 영역에 든 것의 개수와 같다. $p\leftrightarrow q$ 를 바꾸면 직사각형이 대각선으로 대칭 이동하고, 두 영역의 격자점 개수의 합이 정확히 직사각형 전체의 격자점 개수 $\frac{p-1}2\cdot\frac{q-1}2$ 가 된다 — 이것이 우변의 지수다. 즉 상호법칙은 "기하적 대칭(대각선 반사)이 대수적 대칭(두 Legendre 기호의 곱)으로 번역된다"는 진술이다. 또 다른 직관은 유한체의 관점: $\left(\frac pq\right)=1$ 은 "$\mathbb{F}_q$ 에 $\sqrt p$ 가 존재한다"는 뜻이고, 이것이 $q$ 가 특정 환($\mathbb{Z}[\sqrt{p^*}]$, $p^*=\pm p$)에서 어떻게 분해되는지와 동치라는 사실로 이어진다 — 이 시각이 류체론으로 일반화되는 길이다.

정의·정리

정리 (이차상호법칙, Gauss).¹ 서로 다른 홀소수 $p,q$ 에 대해 $$\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}.$$ 우변의 지수 $\frac{p-1}2\cdot\frac{q-1}2$ 는 $p\equiv q\equiv3\pmod4$ 일 때만 홀수이고, 그 외(둘 중 적어도 하나가 $\equiv1\pmod4$)는 짝수다. 따라서:

보충법칙(제1·제2, 이차잉여에서 가져옴). $$\left(\frac{-1}p\right)=(-1)^{\frac{p-1}2},\qquad \left(\frac2p\right)=(-1)^{\frac{p^2-1}8}.$$

이 셋(주법칙 + 두 보충법칙)으로 임의의 Legendre 기호를 계산할 수 있다 — 알고리즘은: (1) 분자를 소인수분해해 곱셈성으로 쪼갠다, (2) $-1,2$ 는 보충법칙으로 직접, 홀소수 인수는 상호법칙으로 분자·분모를 뒤집는다, (3) 뒤집은 후 분자를 분모로 나눈 나머지로 환원해 더 작은 수로 재귀한다. 이는 본질적으로 Euclid 호제법과 같은 구조의 재귀이며, 따라서 매우 빠르게(다항시간) 끝난다 — 직접 $a^{(p-1)/2}$ 를 계산하는 것과 답은 같지만, 손 계산에서는 상호법칙 쪽이 훨씬 간결하다.

주요 정리 (증명 스케치와 일반화)

증명의 구조(개요). 표준 증명(Eisenstein)은 Gauss의 보조정리(Gauss's Lemma)에서 출발한다: $\gcd(a,p)=1$ 일 때 $a,2a,\dots,\frac{p-1}2a$ 를 $\bmod p$ 로 $-\frac p2<r<\frac p2$ 범위의 대표원으로 환원하면, 음수가 된 것의 개수를 $\mu$ 라 할 때 $\left(\frac ap\right)=(-1)^\mu$. 이를 $a=q$ (소수)에 적용하고 $\mu$ 를 격자점 개수로 다시 표현한 뒤, $p\leftrightarrow q$ 대칭을 격자점의 대각선 반사로 구현하면 상호법칙의 지수 공식이 떨어진다. 완전한 세부 증명은 Silverman ch.23에서 전개되며, 이 위키는 구조(격자점 대칭)만 직관 절에서 다뤘다.²

계산 알고리즘으로서의 상호법칙. 임의의 $\left(\frac ap\right)$ 계산은 다음 순서로 종결된다: 1. $a$ 를 $\bmod p$ 로 환원. 2. $a=\pm2^e\cdot m$ ($m$ 홀수)로 인수분해, 곱셈성으로 $\left(\frac{-1}p\right)^{[\pm]}\left(\frac2p\right)^e\left(\frac mp\right)$ 로 분리. 3. $\left(\frac mp\right)$ 에 상호법칙 적용해 $\left(\frac pm\right)$ (부호 보정 포함)으로 뒤집기. 4. $p\bmod m$ 으로 환원해 1로 돌아가 재귀(분모가 점점 작아지므로 유한 단계 종료).

이 절차는 Jacobi 기호로 확장하면(분모가 합성수여도 됨) 소인수분해 없이도 작동해 실제 계산기·암호 구현에서 쓰인다(이 위키 범위 밖이지만 자연스러운 다음 단계).

상호법칙과 등차수열의 소수. 상호법칙의 첫 번째 응용 중 하나는 prime distribution에서 본 Euclid식 논법의 일반화다. 예를 들어 $-1$ 의 보충법칙은 $4k+1$ 형 소수가 무한함을, 제2보충법칙은 $8k\pm1$ 형 소수의 무한성을 비슷한 논법으로 보이는 데 쓰인다 — 일반적인 등차수열에 대한 완전한 결과(Dirichlet 정리)는 해석적 도구가 필요하지만, 특수한 경우는 상호법칙만으로 초등적으로 풀린다.

예제

예제 1 (계산, $\left(\frac{37}{47}\right)$). $37\equiv1\pmod4$ → 부호 안 바뀜: $\left(\frac{37}{47}\right)=\left(\frac{47}{37}\right)=\left(\frac{10}{37}\right)$ ($47\equiv10\bmod37$) $=\left(\frac2{37}\right)\left(\frac5{37}\right)$. $37\equiv5\pmod8$ → $\left(\frac2{37}\right)=-1$. $\left(\frac5{37}\right)$: $5\equiv1\bmod4$ → $=\left(\frac{37}5\right)=\left(\frac25\right)$; $5\equiv5\bmod8$ → $-1$. 곱 $=(-1)(-1)=+1$ → $37$ 은 $\bmod47$ QR.

예제 2 (풀이 가능성 판정). 예제 1로부터 $x^2\equiv37\pmod{47}$ 은 해가 존재한다(값은 모르지만 존재성은 확정). 직접 탐색하면 $x=21$: $21^2=441=9\times47+18$... 검산: $441-9\cdot47=441-423=18\ne37$. 더 찾으면 $x=29$: $29^2=841=17\cdot47+42$; $841-799=42\ne37$. (해의 명시적 구성은 상호법칙의 범위 밖 — Tonelli–Shanks 알고리즘이 필요. 여기서는 존재성만 보장됨에 주의.)

예제 3 (뒤집기 부호, 둘 다 $3\bmod4$). $\left(\dfrac3{7}\right)$: $3\equiv3$, $7\equiv3\pmod4$ → 둘 다 해당 → 부호 반전: $=-\left(\frac73\right)=-\left(\frac13\right)=-(+1)=-1$ → $3$ 은 $\bmod7$ QNR. (직접 확인: $\bmod7$ 의 QR은 $\{1,2,4\}$, $3\notin$.) ✓

예제 4 (체인 계산, $\left(\frac5{11}\right)$). $5\equiv1\pmod4$ → 부호 안 바뀜: $=\left(\frac{11}5\right)=\left(\frac15\right)=+1$.

예제 5 (3중 곱, $\left(\frac{105}{317}\right)$, $317$ 소수, $105=3\cdot5\cdot7$). $317\equiv1\pmod4$ 이므로 $3,5,7$ 어느 것을 뒤집어도 부호는 그대로 유지된다: $\left(\frac{105}{317}\right)=\left(\frac3{317}\right)\left(\frac5{317}\right)\left(\frac7{317}\right)=\left(\frac{317}3\right)\left(\frac{317}5\right)\left(\frac{317}7\right)$. $317\equiv2\bmod3\Rightarrow\left(\frac23\right)=-1$; $317\equiv2\bmod5\Rightarrow\left(\frac25\right)=-1$; $317\equiv2\bmod7\Rightarrow\left(\frac27\right)=+1$. 곱 $=(-1)(-1)(+1)=+1$.

예제 6 (보충법칙과 결합, $\left(\frac{-3}{p}\right)$ 일반 공식). $\left(\frac{-3}p\right)=\left(\frac{-1}p\right)\left(\frac3p\right)$. $p>3$ 일 때 이를 전개하면 $\left(\frac{-3}p\right)=+1\iff p\equiv1\pmod3$ 이라는 깔끔한 결과가 나온다(연습문제 5에서 직접 유도) — 이는 $x^2+3$ 의 소인수가 $\bmod3$ 으로 어떻게 갈리는지를 결정하며, 정수환 $\mathbb{Z}[\omega]$ ($\omega=$ 1의 원시세제곱근)에서 소수 분해 패턴과 연결된다(가우스 정수의 사촌격인 Eisenstein 정수 이야기로, 이 위키 범위 밖).

흔한 오해와 함정

• "상호법칙은 항상 $\left(\frac pq\right)=\left(\frac qp\right)$ 다" — 틀림. $p\equiv q\equiv3\pmod4$ 인 경우엔 부호가 반대다. 조건을 빠뜨리는 것이 가장 흔한 실수.
• "분자가 소수가 아니어도 그대로 상호법칙을 적용한다" — 상호법칙 자체는 분모·분자가 모두 홀소수일 때의 진술이다. 분자가 합성수면 먼저 곱셈성으로 소인수로 쪼개야 한다(예제 5).
• "$2$ 도 상호법칙으로 처리한다" — 아니다. $2$ 는 홀소수가 아니므로 상호법칙의 대상이 아니고, 반드시 제2보충법칙을 별도로 적용해야 한다.
• "상호법칙이 풀이 $x$ 를 알려준다" — 아니다(예제 2). 상호법칙은 풀이 가능성(QR 여부)만 판정하며, 실제 해를 구성하지는 않는다.
• 뒤집은 후 환원을 잊음 — $\left(\frac pq\right)$ 를 $\left(\frac qp\right)$ 로 뒤집은 다음에는 반드시 $q\bmod p$ 로 환원해 더 작은 수로 만들어야 재귀가 종결된다. 환원을 건너뛰면 계산이 끝나지 않는다.

큰 그림 / 연결

이차상호법칙은 이차잉여의 보충법칙과 곱셈성에서 자연스럽게 자라나, 임의의 Legendre 기호 계산을 Euclid 호제법과 똑같은 속도의 알고리즘으로 만든다. 두 제곱수의 합의 Fermat 정리($p=a^2+b^2\iff p\equiv1\pmod4$)는 제1보충법칙의 직접 응용이며, 가우스 정수에서 소수 $p$ 가 분해(split)·불활성(inert)·분기(ramified) 중 어디에 속하는지를 결정하는 기준도 본질적으로 $\left(\frac{-1}p\right)$ 다. 더 가까이는, 원시근의 지표적 구조(QR = 짝수 지표)가 상호법칙의 증명에 깔린 군론적 직관을 제공한다. 역사적·이론적으로 가장 멀리 보면, 상호법칙은 "두 모듈러스에서의 분해 가능성이 서로를 결정한다"는 패턴의 최초 사례이며, 이 패턴이 일반 대수적 수체에서의 Artin 상호법칙, 그리고 류체론·Langlands 프로그램으로 일반화된다 — algebra 위키의 splitting-and-finite-fields에서 다루는 유한체의 구조론이 이 다리의 한쪽 끝이다.

연습문제

1. $\left(\dfrac5{11}\right)$ 을 상호법칙으로 계산하라.
2. $x^2\equiv 3\pmod{53}$ 가 풀리는지 판정하라.
3. $\left(\dfrac{105}{317}\right)$ 을 계산하라 ($317$ 소수, $105=3\cdot5\cdot7$).
4. $7$ 이 $\bmod p$ QR이 되는 $p$ 의 조건을 상호법칙으로 구하라.
5. $\left(\dfrac{-3}p\right)=+1 \iff p\equiv1\pmod3$ 임을 보여라.
6. $\left(\dfrac{15}{31}\right)$ 을 계산하라.
7. $p\equiv1\pmod4$ 이고 $q\equiv1\pmod4$ 인 두 소수에 대해, $p$ 가 $q$ 의 QR이면 $q$ 도 $p$ 의 QR임을 상호법칙으로부터 설명하라.
8. $\left(\dfrac{2}{p}\right)$ 와 $\left(\dfrac{-2}{p}\right)$ 가 같아지는 $p\bmod8$ 의 조건을 구하라.

관련 개념

• 이차잉여 — Legendre 기호·보충법칙
• 두 제곱수의 합 — $-1$ QR 응용
• 원시근 — QR 구조
• prime distribution — 등차수열에서 소수의 초등적 사례에 응용
• 가우스 정수 — 소수의 분해/불활성 판정에 사용