📂정수론

이차잉여와 비이차잉여

정의 ¹

소수 $p \ne 2$ 와 $a < p$ 에 대해 합동방정식 $x^{2} \equiv a \pmod{p}$ 의 해가 존재하면 $a$ 를 모듈로 $p$ 에 대한 이차잉여 QR이라 한다. $a$ 가 이차잉여가 아니면 비이차잉여 NR이라 한다.

설명

쉽게 말해 이차잉여란 $\pmod{p}$에서 제곱근이 존재하는 수를 의미한다.

예를 들어 소수 $7$ 을 생각해보면 $$1^2 \equiv 1 \pmod{7} \\ 2^2 \equiv 4 \pmod{7} \\ 3^2 \equiv 2 \pmod{7} \\ 4^2 \equiv 2 \pmod{7} \\ 5^2 \equiv 4 \pmod{7} \\ 6^2 \equiv 1 \pmod{7}$$ $1,2,4$ 는 QR이고 $3,5,6$ 은 NR이다.소수 $11$ 을 생각해보면 $$1^2 \equiv 1 \pmod{11} \\ 2^2 \equiv 4 \pmod{11} \\ 3^2 \equiv 9 \pmod{11} \\ 4^2 \equiv 5 \pmod{11} \\ 5^2 \equiv 3 \pmod{11} \\ 6^2 \equiv 3 \pmod{11} \\ 7^2 \equiv 5 \pmod{11} \\ 8^2 \equiv 9 \pmod{11} \\ 9^2 \equiv 4 \pmod{11} \\ 10^2 \equiv 1 \pmod{11}$$ $1,3,4,5,9$ 가 QR이고 나머지 $2,6,7,8,10$ 은 NR이다.재미있게도 QR은 대칭적으로 나타나는데, 사실 $$(p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p}$$ 이므로 당연하다. 또한 항상 QR과 NR은 정확히 같은 개수만큼 나타난다.

정리

$2$ 보다 큰 소수 $p$ 에 대해 QR과 NR은 정확히 $\displaystyle {(p-1) \over 2}$ 개 존재한다.

증명

$1$ 부터 $p-1$ 까지의 모든 수를 제곱한 목록은 다음과 같다. $$1^2, 2^2, \cdots , (p-1)^2$$ 그런데 앞서 살펴봤듯 $$(p-q)^2 \equiv p^2-2pq+q^2 \equiv q^2 \pmod{p}$$ 이므로 $1$ 을 보나 $p-1$ 을 보나 마찬가지고, $2$ 를 보나 $p-2$ 를 보나 마찬가지다. 따라서 우리는 원래의 절반인 $$1^2, 2^2, \cdots , \left( {{ p-1 } \over { 2 }} \right)^2$$ 만 살펴보면 충분하다. 이 수들은 QR의 정의에 따라 모두 QR이므로, 이 수들이 모두 서로 다르다는 걸 보이면 QR이 정확히 $\displaystyle {(p-1) \over 2}$ 개 존재한다고 할 수 있을 것이다. 마찬가지로, $\pmod{p}$ 에서 $p$보다 작은 자연수는 QR이 아니면 NR이므로 QR이 정확히 $\displaystyle {(p-1) \over 2}$ 개 존재한다면 NR 역시 정확히 $\displaystyle {(p-1) \over 2}$ 개 존재할 것이다.본격적인 증명은 귀류법을 사용한다. $b_1$ 과 $b_2$ 를 $\displaystyle {{(p-1)} \over {2}}$ 보다 작은 서로 다른 두 자연수라고 하자.

${b_1}^2 \equiv {b_2}^2 \pmod{p}$ 이 성립한다고 가정하면 $${b_1}^2 - {b_2}^2 \equiv 0 \pmod{p}$$ 따라서 어떤 정수 $k$ 에 대해 ${b_1}^2 - {b_2}^2 = pk$ 이고, 소수 $p$ 는 $({b_1} + {b_2})({b_1} - {b_2})$ 의 약수다. 하지만 $b_1$ 과 $b_2$ 이 $\displaystyle {{(p-1)} \over {2}}$ 보다 작다고 했으므로 $({b_1} + {b_2})$ 는 $(p-1)$ 보다 작다. $p$ 는 $({b_1} + {b_2})$ 의 약수가 될 수 없으므로 반드시 $({b_1} - {b_2})$ 의 약수여야한다. 그러나 마찬가지의 이유로 $|{b_1} - {b_2}|$ 는 $(p-1)$ 보다 작으므로 $0$ 이어야만 $p$ 로 나눠질 수 있다. 즉, ${b_1} = {b_2}$ 인데 $b_1$ 과 $b_2$ 는 $\displaystyle {{(p-1)} \over {2}}$ 보다 작은 서로 다른 두 자연수로 가정했으므로 모순이다. 따라서 ${b_1}^2 \neq {b_2}^2 \pmod{p}$ 이고, QR은 정확히 $\displaystyle {(p-1) \over 2}$ 개 존재한다.

■