핵심 명제
소수 p에 대해 r이 primitive root이고 a = r^m이라 하자.
m이 짝수이면a는 quadratic residue이다.m이 홀수이면a는 quadratic non-residue이다.
직관
QR은 어떤 수의 제곱으로 표현되는 수다.
m = 2k이면 다음과 같이 쓸 수 있다.
r^m = r^(2k) = (r^k)^2따라서 r^m은 제곱 꼴이므로 QR이다.
반대로 primitive root의 거듭제곱들은 1부터 p-1까지의 모든 nonzero residue를 한 번씩 만들고, 그중 제곱으로 나오는 것들은 정확히 짝수 지수 쪽에 대응된다.