Proof Quadratic Residues

DoMath
둘러보기로 이동 검색으로 이동
제곱꼴 나머지 로 돌아가기

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

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

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

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

  • 가 해를 z로 가지면, -z 도 해가 된다.
  • 앞에서 z 와 -z 는 p 의 모듈합동이 아니다.
  • 이 둘 말고는 모듈합동이 아닌 다른 해는 없다.

주어진 p 와 a 에 대하여 의 해가 있다면, 그 해를 z 라 하자. 그렇다면 (-z) 도 해가 될 것이다. 왜냐하면 모듈합동의 성질에 따라,

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

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

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

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

이다. 따라서

이거나

이고

이거나

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


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

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

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