법 $p$에서 어떤 수가 ‘제곱수’인지를 묻는 문제이다. 예를 들어 법 $7$에서 제곱수는 $1,2,4$뿐이다. 가우스가 ‘황금 정리’라 부른 이차상호법칙은 서로 다른 두 소수 사이의 이 관계를 놀라울 만큼 간단하게 연결한다.
핵심 개념
- $p\nmid a$이고 $x^2\equiv a\pmod p$의 해가 있으면 $a$를 법 $p$의 이차잉여, 없으면 이차비잉여라 한다.
- 르장드르 기호: $\left(\frac ap\right)=1$ (이차잉여), $-1$ (비잉여), $0$ ($p\mid a$)
- 홀수 소수 $p$에 대해 이차잉여와 비잉여는 각각 $\frac{p-1}{2}$개씩이다.
핵심 정리
- 오일러 판정법: $\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p$
- $\left(\frac{-1}{p}\right)=1\iff p\equiv1\pmod4$
- 이차상호법칙: 서로 다른 홀수 소수 $p,q$에 대해 $\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}$
증명 보기
잉여가 절반. $1^2,2^2,\dots,(p-1)^2$에서 $x^2\equiv(p-x)^2$이므로 서로 다른 값은 많아야 $\frac{p-1}{2}$개이다. 또 $1\le x<y\le\frac{p-1}2$이면 $x^2\equiv y^2$은 $p\mid(y-x)(y+x)$를 뜻하는데 두 인수 모두 $p$보다 작은 양수이므로 불가능하다. 따라서 정확히 $\frac{p-1}{2}$개이다.
오일러 판정법. 페르마의 소정리에서 $a^{p-1}-1=\left(a^{\frac{p-1}2}-1\right)\left(a^{\frac{p-1}2}+1\right)\equiv0$이므로 $a^{\frac{p-1}{2}}\equiv\pm1$이다. $a\equiv x^2$이면 $a^{\frac{p-1}{2}}\equiv x^{p-1}\equiv1$이다. 그런데 다항식 $t^{\frac{p-1}{2}}-1$은 체 $\mathbb Z_p$에서 근이 많아야 $\frac{p-1}{2}$개이고, 이차잉여 $\frac{p-1}{2}$개가 이미 모두 근이다. 따라서 비잉여에서는 $a^{\frac{p-1}{2}}\equiv-1$이다.
$-1$의 경우. 오일러 판정법에 의해 $\left(\frac{-1}p\right)\equiv(-1)^{\frac{p-1}2}$이고, 이 값은 $\frac{p-1}{2}$이 짝수, 즉 $p\equiv1\pmod4$일 때 $1$이다.
(이차상호법칙의 증명은 가우스 보조정리와 격자점 세기를 이용하며, 대학 정수론 교재에서 다룬다.) $\blacksquare$
예제
- 법 $11$의 제곱: $1,4,9,5,3$ ($1^2$부터 $5^2$까지)이므로 이차잉여는 $\{1,3,4,5,9\}$
- $x^2\equiv-1\pmod{13}$은 $13\equiv1\pmod4$이므로 해가 있다: $5^2=25\equiv-1$
- $\left(\frac{3}{7}\right)$: $3^3=27\equiv-1\pmod7$이므로 $-1$, 비잉여
확인 문제
$x^2\equiv5\pmod{19}$의 해가 있는지 이차상호법칙으로 판정하시오.
풀이 보기
$\left(\frac5{19}\right)\left(\frac{19}5\right)=(-1)^{2\cdot9}=1$이므로 $\left(\frac5{19}\right)=\left(\frac{19}5\right)=\left(\frac45\right)=1$이다 ($4=2^2$). 해가 있다. 실제로 $9^2=81=4\cdot19+5$이다.
정리
- 법 $p$의 이차잉여는 절반, 판정은 $a^{\frac{p-1}2}\equiv\pm1$
- $-1$은 $p\equiv1\pmod4$일 때만 제곱수
