위수 = p-1을 잘 써먹어야 한다.p가 홀수인 소수이고 g가 법 p에 대한 원시근이라고 하자. g^k가 법 p에 대해서 이차잉여이기 위한 필요충분조건은 k가 짝수라는 것을 증명하여라. ( g^k=QR k = 2t라고 하자.g^k = QR 이라는 것은 g^k ≡ x^2 (mod p)인 x가 존재한다는 뜻이다.g^t ≡ g^2t ≡ (g^t)^2 (mod p)이므로x = g^t로 존재하므로 참이다. (=>) g^k=QR => k=짝수 홀수, 짝수 조건이 더 다루기 쉬우므로, 대우명제를 이용하면,k=홀수 => g^k = NR을 증명하면 된다. k = 2t + 1이라 하자p = 홀수 소수, gcd(g, p) = 1 이므로 오일러 판별법에 의해,(g^k)^((p-1)/2) ≡ (g/p) (mod p)≡ g^(p..