이차잉여

개요 — 동기·문제의식

합동방정식 $ax\equiv b\pmod m$ (합동식)은 일차고, 항상 풀이 여부를 $\gcd$ 로 즉시 판정할 수 있었다. 다음 단계는 자연스럽다 — 이차 합동방정식 $x^2\equiv a\pmod p$ 는 언제 풀리는가? 이것은 $a$ 가 $\bmod p$ 에서 "제곱수"인지 묻는 것과 같다. 정수에서는 제곱인지 아닌지가 뻔하지만(근호를 취해보면 된다), 모듈러 세계에서는 $a$ 가 작아 보여도 제곱일 수도 아닐 수도 있어서 패턴이 즉시 보이지 않는다. Silverman은 이 질문을 실험으로 시작한다 — 작은 소수마다 표를 만들어 어떤 $a$ 가 제곱이 되는지 나열하면, 정확히 절반이 "예", 절반이 "아니오"라는 놀라운 규칙성이 드러난다.⁵ 이 규칙성을 추적하면 Legendre 기호라는 부호 표기, Euler의 효율적 판정법, 그리고 궁극적으로 이차상호법칙이라는 정수론의 보석에 도달한다. 더 나아가 이 장은 두 제곱수의 합·원시근·가우스 정수까지 이어지는 정수론 후반부 전체의 출발점이다.

직관

$\bmod p$ 의 0이 아닌 잉여류 $\{1,2,\dots,p-1\}$ 을 제곱사상 $x\mapsto x^2\bmod p$ 으로 보내보자. $p$ 가 소수이면 이 사상은 정확히 2-대-1이다 — $x^2\equiv(-x)^2\pmod p$ 이고, $x\ne-x\pmod p$ (홀소수이므로 $x\equiv0$ 이 아닌 한 $x\ne p-x$)이기 때문이다. 즉 $1,2,\dots,p-1$ 을 짝 $\{x,p-x\}$ 로 묶으면 각 쌍이 같은 제곱값을 내놓으므로, 서로 다른 제곱값(=이차잉여)은 많아야 $\frac{p-1}2$ 개다. 실제로 정확히 그만큼 나온다는 것이 핵심 정리다. 그림으로 보면: $0$ 아닌 잉여류 전체를 둘로 쪼개는 보이지 않는 "체"가 있고, 그 체의 두 칸(QR과 QNR)이 정확히 같은 크기라는 것. Legendre 기호 $\left(\frac ap\right)$ 는 이 체의 어느 칸에 $a$ 가 떨어지는지를 $\pm1$ 부호 하나로 압축한 표기이며, 곱셈성 덕분에 이 부호들은 군의 지표(character)처럼 행동한다 — QR·QR, QNR·QNR 은 QR(부호 같으면 곱은 $+$), QR·QNR 은 QNR(부호 다르면 곱은 $-$), 마치 양수·음수의 곱셈 규칙과 같다.

정의

홀소수 $p$, 정수 $a$ 에 대해 $\gcd(a,p)=1$ 이라 하자.¹

주의(정의역). Legendre 기호는 분모가 반드시 홀소수여야 정의된다(일반 합성수에 대한 확장은 Jacobi 기호로, 이 위키 범위 밖). $a$ 는 임의의 정수를 대입할 수 있으며 $a\bmod p$ 에만 의존한다 — 즉 $\left(\frac ap\right)=\left(\frac{a+p}p\right)$.

참고($p=2$ 제외 이유). $p=2$ 는 위 정의에서 제외된다 — $\bmod2$ 에는 0이 아닌 잉여류가 $\{1\}$ 하나뿐이라 "절반"이라는 개념 자체가 성립하지 않는다. 2와 관련된 이차잉여 질문은 따로 보충법칙으로 다룬다.

주요 정리

정리 (QR의 개수).² 홀소수 $p$ 에 대해, $\bmod p$ 의 0 아닌 잉여류 $p-1$ 개 중 정확히 $\frac{p-1}2$ 개가 이차잉여, 나머지 $\frac{p-1}2$ 개가 이차비잉여다.

정리 (Euler 판정법).³ 홀소수 $p$, $\gcd(a,p)=1$ 이면 $$\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p.$$

정리 (곱셈성, 완전 곱셈적 지표).⁴ $\left(\dfrac{ab}p\right)=\left(\dfrac ap\right)\left(\dfrac bp\right)$.

정리 (제1보충법칙, $-1$).⁴ $\left(\dfrac{-1}p\right)=(-1)^{(p-1)/2}$, 즉 $-1$ 은 $p\equiv1\pmod4$ 일 때 QR, $p\equiv3\pmod4$ 일 때 QNR.

정리 (제2보충법칙, $2$).⁴ $\left(\dfrac2p\right)=(-1)^{(p^2-1)/8}$, 즉 $2$ 는 $p\equiv\pm1\pmod8$ 일 때 QR, $p\equiv\pm3\pmod8$ 일 때 QNR. (증명은 Gauss 보조정리를 이용하며 Euler 판정법보다 정교하다; 이차 상호법칙에서 상호법칙과 함께 자세히 다룸.)

예제

예제 1 (QR 목록 직접 계산, $p=7$). $1^2=1,2^2=4,3^2=2,4^2\equiv2,5^2\equiv4,6^2\equiv1\pmod7$ (대칭 $x,p-x$ 확인). 서로 다른 값은 QR $=\{1,2,4\}$, QNR $=\{3,5,6\}$ — 정확히 $\frac{7-1}2=3$ 개씩.

예제 2 (Euler 판정, $p=7$). $\left(\dfrac37\right)\equiv3^3=27\equiv-1\equiv6\pmod7$ → $3$ 은 QNR. 예제 1의 목록과 일치($3\notin\{1,2,4\}$). ✓

예제 3 (제1보충법칙, $p=13$ vs $p=7$). $13\equiv1\pmod4$ → $\left(\frac{-1}{13}\right)=+1$; 실제로 $5^2=25\equiv-1\pmod{13}$ ✓. $7\equiv3\pmod4$ → $\left(\frac{-1}7\right)=-1$; 예제 1의 QNR 목록에 $6\equiv-1$ 있음 ✓.

예제 4 (제2보충법칙, $p=17$). $17\equiv1\pmod8$ → $\left(\frac2{17}\right)=+1$. 확인: $6^2=36\equiv2\pmod{17}$ ✓.

예제 5 (곱셈성으로 빠른 계산, $p=11$). $\left(\dfrac{12}{11}\right)=\left(\dfrac{1}{11}\right)=1$ (단순 대입이지만), $\left(\dfrac{-4}{11}\right)=\left(\dfrac{-1}{11}\right)\left(\dfrac{4}{11}\right)=(-1)\cdot(+1)=-1$ ($11\equiv3\pmod4$ 라 $-1$ QNR, $4=2^2$ 은 항상 QR).

예제 6 (큰 수에 Euler 판정 + 반복제곱, $p=23$). $\left(\dfrac5{23}\right)\equiv5^{11}\pmod{23}$. $5^2=25\equiv2$, $5^4\equiv4$, $5^8\equiv16$, $5^{11}=5^8\cdot5^2\cdot5^1\equiv16\cdot2\cdot5=160\equiv160-6\cdot23=160-138=22\equiv-1\pmod{23}$ → QNR. (직접 $x^2$ 12개를 다 계산하지 않고 답을 얻음 — 이것이 Euler 판정법의 실용적 위력이다.)

예제 7 (QR이 아닌 합성수 모듈러스의 함정). $\bmod15$ 에서 $1,4,9,16\equiv1,25\equiv10,\dots$ 처럼 제곱의 패턴이 절반-절반으로 깔끔히 갈리지 않는다 — $4^2=16\equiv1$, $7^2=49\equiv4$ 등 대칭이 $\gcd(x,15)>1$ 인 경우 깨진다. 이것이 정리들이 소수 모듈러스에 한정되는 이유를 보여주는 반례다.

예제 8 (음수 인자를 포함한 다단계 곱셈성 계산, $p=29$). $\left(\dfrac{-7}{29}\right)=\left(\dfrac{-1}{29}\right)\left(\dfrac{7}{29}\right)$. $29\equiv1\pmod4$ → $\left(\frac{-1}{29}\right)=+1$. $\left(\frac7{29}\right)\equiv7^{14}\pmod{29}$: $7^2=49\equiv20$, $7^4\equiv20^2=400\equiv400-13\cdot29=400-377=23$, $7^8\equiv23^2=529\equiv529-18\cdot29=529-522=7$, $7^{14}=7^8\cdot7^4\cdot7^2\equiv7\cdot23\cdot20$. $7\cdot23=161\equiv161-5\cdot29=16$, $16\cdot20=320\equiv320-11\cdot29=1$ → $\left(\frac7{29}\right)=+1$. 따라서 $\left(\frac{-7}{29}\right)=(+1)(+1)=+1$ — $-7\equiv22\pmod{29}$ 은 QR(QR 목록 $\{1,4,5,6,7,9,13,16,20,22,23,24,25,28\}$에 $22$ 있음 ✓).

흔한 오해와 함정

• "이차잉여는 항상 작은 수다" — 틀림. QR/QNR 여부는 $a$ 의 크기가 아니라 $a\bmod p$ 의 값과 $p$ 의 합동류에 의존한다. 큰 $a$ 도 작은 $a\bmod p$ 로 환원해서 판정한다.
• "Euler 판정법이 해 $x$ 자체를 알려준다" — 아니다. $a^{(p-1)/2}\bmod p$ 는 $\pm1$ 중 어느 것인지만 알려줄 뿐, $x^2\equiv a$ 의 실제 해 $x$ 를 구성하지 않는다(해를 구성하는 방법은 $p\equiv3\pmod4$ 일 때 $x=a^{(p+1)/4}$ 같은 특수 공식이나 Tonelli–Shanks 알고리즘 별도 필요).
• "QR끼리 더하면 QR" — 틀림. 곱셈성만 성립하고 덧셈에는 아무 규칙이 없다. 예: $\bmod7$ 에서 $1,2$ 모두 QR이지만 $1+2=3$ 은 QNR.
• "$p$ 가 합성수여도 정리가 그대로 성립한다" — 위 예제 7에서 보듯 거짓. 정리들은 모두 $p$ 가 홀소수임을 본질적으로 사용한다(제곱사상이 정확히 2-대-1 이려면 영인자가 없어야 한다).
• 보충법칙의 조건을 $p\bmod4$ 와 $p\bmod8$ 로 헷갈림 — $-1$ 은 $\bmod4$, $2$ 는 $\bmod8$ 로 결정된다는 것을 정확히 구분해야 한다.

큰 그림 / 연결

이차잉여는 "어떤 수가 어떤 모듈러스에서 제곱인가"라는 단일 질문에서 출발해 정수론 후반부 전체로 갈라지는 분기점이다. Legendre 기호의 곱셈성과 보충법칙을 모으면 이차상호법칙이 완성되어, 임의의 $\left(\frac ap\right)$ 를 (소인수분해 후) 상호법칙의 반복 적용만으로 계산할 수 있게 된다. $-1$ 의 보충법칙은 두 제곱수의 합 정리의 핵심 보조정리이며($p=a^2+b^2\iff p\equiv1\pmod4$ 의 필요성 쪽), 이는 다시 가우스 정수 $\mathbb{Z}[i]$ 에서 소수가 분해되는지 불활성인지를 결정하는 기준이 된다. 또한 원시근의 관점에서 QR은 정확히 원시근의 짝수 거듭제곱들이며, 이 지표적 시각은 algebra 위키의 유한체 곱셈군의 구조와 정확히 같은 현상이다. 더 멀리는, Legendre 기호를 합성수 모듈러스로 확장한 Jacobi 기호, 그리고 더 일반적인 모듈러스에서의 거듭제곱잉여(power residue) 이론이 류체론(class field theory)으로 이어진다.

연습문제

1. $\bmod 11$ 의 이차잉여를 모두 구하라.
2. Euler 판정으로 $\left(\dfrac5{11}\right)$ 을 구하라.
3. $\left(\dfrac{-1}p\right)$ 의 보충법칙으로 $-1$ 이 QR인 소수 $p<30$ 을 나열하라.
4. $x^2\equiv2\pmod7$ 가 풀리는지 판정하라.
5. QR끼리의 곱이 QR임을 곱셈성으로 보여라.
6. $\left(\dfrac{18}{23}\right)$ 을 곱셈성과 보충법칙으로 계산하라($18=2\cdot3^2$).
7. $p=29$ 에서 $2$ 가 QR인지 보충법칙으로 판정하고, 직접 제곱으로 확인하라.
8. $\bmod p$ 에서 QNR의 개수가 QR의 개수와 같다는 사실을 이용해, $\sum_{a=1}^{p-1}\left(\frac ap\right)=0$ 임을 설명하라.

관련 개념

• 이차 상호법칙 — $\left(\frac pq\right)$ 와 $\left(\frac qp\right)$ 의 관계
• 합동식 · 페르마 소정리 — Euler 판정의 기초
• 두 제곱수의 합 — $-1$ 이 QR인 소수
• 원시근 — QR = 짝수 지표
• 가우스 정수 — $-1$ 의 QR 여부가 가우스 소수 분해를 결정