이차합동식의 핵심은 어떤 수가 modulo 에서 제곱이 될 수 있는지를 판정하는 것이다. 홀수 소수 법에서는 이 문제가 Euler’s Criterion과 Legendre Symbol로 정리된다.
이차합동식과 판별식
가 홀수 소수이고 일 때
에 를 곱하면
이다. 따라서 일반 이차합동식의 해 존재 여부는 판별식
이 modulo 에서 제곱인지 여부로 환원된다.
Quadratic Residue
일 때
가 해를 가지면 를 quadratic residue, 해가 없으면 quadratic nonresidue라고 한다.
와 는 같은 제곱을 만들며, 의 제곱들은 서로 다르다. 따라서 0이 아닌 residue 중 정확히
개가 quadratic residue이고 나머지 절반이 nonresidue이다.
원시근 를 사용하면 모든 는 으로 표현되고, 가 제곱일 필요충분조건은 이 짝수인 것이다.
Euler’s Criterion
가 홀수 소수이고 이면
증명
라 하자. 의 order는 이므로
이다. 이 짝수이면 는 제곱이고 값은 1이다. 홀수이면 비제곱이고 값은 -1이다.
또는 Fermat 정리에서
이므로 가능한 값이 뿐이라는 것도 확인할 수 있다.
Legendre Symbol
홀수 소수 에 대해
로 정의한다. Euler’s Criterion은
라고 쓸 수 있다. 양변의 값은 중 하나이므로 합동값으로 symbol의 실제 값을 결정할 수 있다.
기본 성질
곱셈성은 Euler criterion에서
을 사용하면 얻는다.
의 이차잉여성
Euler criterion으로
이다. 따라서 은 일 때만 풀린다.
예제
의 해 존재를 판정하자. 이고
이므로 5는 quadratic nonresidue이며 해가 없다.
꼴 소수의 무한성
그러한 소수가 유한하여 뿐이라고 가정하자. 다음 수를 잡는다.
의 홀수 소인수 에 대해
이므로 -1은 modulo 의 quadratic residue이다. 따라서 이다. 그런데 어떤 도 을 나누지 않으므로 새로운 꼴 소수를 얻어 모순이다.
Legendre Symbol의 합
quadratic residue와 nonresidue가 각각 같은 수만큼 있으므로
이다. 원시근 를 사용하면 symbol 값이 로 번갈아 나타나는 것으로도 볼 수 있다.
정리
이차합동식은 판별식이 quadratic residue인지 판정하는 문제로 환원된다. Euler’s Criterion은 거듭제곱 하나로 residue 여부를 결정하며 Legendre Symbol은 그 결과를 계산하기 쉬운 기호로 정리한다.
연습 문제
- modulo 13의 0이 아닌 quadratic residue를 모두 구한다.
- 을 계산한다.
- 의 해 존재 여부를 판정한다.
풀이
1번
만 계산하면 되고
이므로 집합은 이다.
2번
이므로 값은 -1이다.
3번
판별식은
이다. modulo 11의 quadratic residue는 이므로 해가 존재한다.