Euler’s Criterion은 Legendre Symbol을 계산할 수 있지만 지수가 크면 번거롭다. Gauss’s Lemma와 Quadratic Reciprocity는 큰 수에 대한 symbol을 작은 수로 반복해서 바꾸는 계산법을 제공한다.
Gauss’s Lemma
홀수 소수 와 에 대해
의 least absolute residues를 취한다. 그중 음수인 것, 동치로 least positive residue가 보다 큰 것의 개수를 이라 하자.
증명
각 residue의 절댓값을 라 하자. 이들은 의 순열이다. 따라서
이다. factorial을 약분하고 Euler’s Criterion을 적용하면 결과를 얻는다.
첫 번째 보충법칙
이면 모든 가 음의 residue를 만들므로
이다.
두 번째 보충법칙
일 때 가 되는 항의 개수를 세면
이다. 지수 의 parity는 의 modulo 8 값만으로 결정된다.
Floor Sum Form
Gauss’s Lemma는 다음 형태로도 쓸 수 있다.
각 를 로 나눈 몫의 parity가 residue가 상반부로 넘어가는 횟수를 기록한다.
Quadratic Reciprocity Law
서로 다른 홀수 소수 에 대해
이다. 즉 둘 중 하나가 이면 symbol을 그대로 뒤집을 수 있고, 둘 다 이면 부호가 바뀐다.
격자점 증명의 핵심
직사각형
의 격자점을 직선 위아래로 나눈다. 직선 위에는 격자점이 없고 전체 개수는 이다. 두 영역의 격자점 수는 각각 Gauss floor sum의 지수가 되므로 parity를 비교하면 reciprocity law를 얻는다.
계산 예제
을 계산하자. 29와 53은 모두 이므로
이다. 이므로
이다. 이므로 첫 항은 -1이고, reciprocity를 사용하면 이므로 전체 값은 1이다.
Jacobi Symbol
홀수 양의 정수
에 대해 Jacobi symbol을
로 정의한다. Legendre Symbol의 곱셈성, 두 보충법칙, reciprocity law는 Jacobi symbol에도 같은 계산 규칙으로 확장된다.
특히
이고 서로소인 홀수 에 대해
이다.
Jacobi Symbol의 주의점
이면 는 modulo 의 제곱이 아니다. 그러나 값이 1이라고 해서 반드시 제곱인 것은 아니다. 예를 들어
이지만 는 해가 없다. Jacobi symbol은 여러 소수 법의 부호를 곱하므로 두 nonresidue가 상쇄될 수 있다.
정리
Gauss’s Lemma는 배수의 residue가 상반부로 넘어가는 횟수로 Legendre Symbol을 계산한다. 두 보충법칙과 Quadratic Reciprocity는 symbol을 빠르게 축소한다. Jacobi Symbol은 같은 계산 규칙을 합성수 분모에 확장하지만, 값 1을 quadratic residue의 충분조건으로 해석하면 안 된다.
연습 문제
- 을 계산한다.
- 을 quadratic reciprocity로 계산한다.
- 을 계산하고 그 값의 의미를 설명한다.
풀이
1번
이므로 값은 1이다.
2번
둘 다 이므로
이다. 이고 이므로 이다. 따라서 값은 1이다.
3번
이다. 그러나 분모가 합성수이므로 이것만으로 가 modulo 45의 quadratic residue라고 결론내릴 수는 없다.