Proof Quadratic Residues

제곱꼴 나머지 로 돌아가기

제곱꼴 나머지 부분 증명 모음

p 보다 작은 수중, p 의 제곱꼴 나머지는 반이다

기초정리  : p 가 홀수인 소수고 a 가 p 의 배수가 아니라면, 제곱꼴 나머지가 있을 경우 서로 모듈합동이 아닌 제곱꼴 나머지는 꼭 두 개 뿐이다.

다음을 차례대로 보일 것이다. (스스로 해보라.)

• $x^{2}\equiv a\ \qquad ({\rm {modp)}}$ 가 해를 z로 가지면, -z 도 해가 된다.
• 앞에서 z 와 -z 는 p 의 모듈합동이 아니다.
• 이 둘 말고는 모듈합동이 아닌 다른 해는 없다.

주어진 p 와 a 에 대하여 $x^{2}\equiv a\ \quad ({\rm {modp)}}$ 의 해가 있다면, 그 해를 z 라 하자. 그렇다면 (-z) 도 해가 될 것이다. 왜냐하면 모듈합동의 성질에 따라,

$z^{2}\equiv (-z)^{2}\equiv a\ \quad ({\rm {modp)}}$

이기 때문이다. 여기서 만약

$z\equiv (-z)\ \quad ({\rm {modp)\ \quad \Rightarrow \ 2z\equiv 0\ \quad ({\rm {modp)}}}}$

이 되고 이것은 명백히 잘못이다. 2z 는 짝수고 p 는 홀수인 소수다. 문제의 조건과 어긋난다.

이제 z 라는 해가 있을 경우, -z 말고는 없다는 사실을 보이자. 이를 위해 z' 가 따로 있다고 가정해본다. 다시 말해,

$z^{2}\equiv (z')^{2}\equiv a\ \quad ({\rm {modp)}}$

인 것이다. 그렇다면 모듈합동의 성질에 따라,

$z^{2}-(z')^{2}\equiv (z-z')(z+z')\equiv 0\ \quad ({\rm {modp)}}$

이다. 따라서

$(z-z')\equiv 0\ \quad ({\rm {modp)}}$ 이거나 $(z+z')\equiv 0\ \quad ({\rm {modp)}}$

이고

$z\equiv z'\ \quad ({\rm {modp)}}$ 이거나 $z\equiv -z'\ \quad ({\rm {modp)}}$

이다. z 와 -z 와 모듈 합동이 아닌 다른 제곱꼴 나머지는 없다. 증명 끝.

정리 : p 가 홀수인 소수고 a 가 p 의 배수가 아니라면, p 보다 작은 수 중, p 의 제곱꼴 나머지는 반이다.

p 보다 작은 수들 1 , 2, 3, ... , p-1 에 대하여 가능한 제곱꼴의 개수는 p-1 개다. 만약 그 수들 중 어떤 수 a 가 제곱꼴 나머지라면 기초정리에 따라 그 때의 a 에 대해 한 쌍이 되는 z 와 (-z) 가 모두 해가 된다. $x^{2}\equiv (p-x)^{2}\ ({\rm {modp)}}$ 인 관계에 있는, (1,p-1) , (2,p-2) , ... , $\left({\frac {p-1}{2}},{\frac {p+1}{2}}\right)$ 들이다. 이것들의 개수는${\frac {p-1}{2}}$ 개다.

7 에 대하여 제곱꼴 나머지들은 1, 2, 4 와 7-합동관계에 있는 수들이고, 제곱꼴 非나머지들은 3, 5, 6 과 7-합동관계다. 일반적으로 주어진 소수 p 에 대한 제곱꼴 나머지는 $1^{2},2^{2},\cdots ,(p-1)^{2}$ 들과 p-모듈 합동 관계인 수들로 되어 있다. 그런데 이것들은 앞의 예에서 $1^{2}\equiv _{7}6^{2},\ 2^{2}\equiv _{7}5^{2},\ 3^{2}\equiv _{7}4^{2}$ 로 드러나듯 둘씩 짝을 지어 합동관계이므로 1 부터 p-1까지 수들 중 반만 제곱꼴 나머지가 된다.