이차 나머지

위키백과 ― 우리 모두의 백과사전.

수학에서 정수 an에 대한 이차 나머지(quadratic residue)라고 하는 것은 a가 어떤 정수의 제곱을 n으로 나눈 나머지와 같을 때, 즉, 적당한 정수 x

x^2 \equiv a \pmod{n}

을 만족할 때를 뜻한다. 위의 이차 합동식을 만족하는 해가 없을 때, a를 이차 나머지가 아니라고 한다(quadratic non-residue).

예를 들어,

1^2 \equiv 1, 3^2 \equiv 2, 2^2 \equiv 4 \pmod{7}

이므로, 1, 2, 4는 7에 대한 이차 나머지이다. 한편, 2, 5, 6은 7에 대한 이차 나머지가 아니다. 일반적으로 홀수인 소수 p\,에 대하여 1, 2, \cdots, p-1 가운데 이차 나머지인 수와 이차 나머지가 아닌 수는 각각 \frac{p-1}{2} 개씩 존재한다.

두 홀수 소수 p, q\,가 서로에 대해 이차 나머지인지 아닌지는 이차상호법칙이라 부르는 대칭적인 관계가 성립한다.