1.5 이차잉여 (Quadratic Residues)

이차잉여는 방정식 $x^2 \equiv a \pmod p$의 해가 존재하는지를 다룹니다. 이는 정수론의 가장 아름다운 정리 중 하나인 이차 상호 법칙으로 이어집니다.

1. 이차잉여의 정의와 르장드르 기호

홀수인 소수 $p$와 $\gcd(a, p)=1$인 정수 $a$에 대하여, $x^2 \equiv a \pmod p$를 만족하는 정수 $x$가 존재하면 $a$를 이차잉여(QR), 존재하지 않으면 이차비잉여(QNR)라고 합니다.

Legendre Symbol

$$\left( \frac{a}{p} \right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue mod } p \\ -1 & \text{if } a \text{ is a quadratic non-residue mod } p \\ 0 & \text{if } p \mid a \end{cases}$$

2. 오일러 판정법 (Euler's Criterion)

르장드르 기호의 값을 실제로 계산할 수 있게 해주는 강력한 도구입니다.

$$\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod p$$

성질: $\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)$ 이 성립하며, 이는 르장드르 기호가 곱셈적(multiplicative)임을 보여줍니다.

3. 이차 상호 법칙 (Law of Quadratic Reciprocity)

가우스가 "수학의 여왕의 보석"이라 칭송한 이 정리는 두 소수 $p, q$ 사이의 이차잉여 관계를 연결합니다.

서로 다른 홀수 소수 $p, q$에 대하여 다음이 성립합니다.

$$\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$$

즉, $p$와 $q$가 모두 $4n+3$ 꼴인 경우에만 두 기호의 값이 반대이고, 그 외에는 같습니다.

4. 제1, 제2 보충 법칙

제1 보충 법칙: $\left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}$ ($p \equiv 1 \pmod 4$ 이면 1)

제2 보충 법칙: $\left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8}$ ($p \equiv 1, 7 \pmod 8$ 이면 1)