Legendre Symbol은 modulo 에서 제곱근의 존재 여부를 판정한다. 실제로 modulo 또는 합성수에서 해를 구하려면 소수 법의 해를 단계적으로 올리고 CRT로 결합해야 한다.
에서의 명시적 제곱근
가 quadratic residue이고 이면
가 해이다. 실제로
이며 Euler’s Criterion을 사용했다.
Hensel Lifting의 기본 아이디어
인 해 를 알고 있다고 하자. 다음 단계의 해를
로 놓는다. 전개하면
이다. 로 쓰고 modulo 만 보면 는 사라지므로
를 풀면 된다.
가 홀수이고 이면 이며 가 invertible이다. 따라서 가 modulo 에서 유일하고 각 root는 다음 단계로 유일하게 lift된다.
예제:
먼저 modulo 7에서
이고 root는 이다.
에서 이므로
이고 이다. 따라서 이다.
에서는 이므로
에서 이고 이다. 따라서
이다.
일반 Hensel Lemma 관점
다항식 에 대해 이고
이면 는 각 로 유일하게 lift된다. 이차식 에서는 derivative가 이므로 위의 조건과 정확히 일치한다.
Derivative가 0인 singular root에서는 lift가 없거나 여러 개 생길 수 있어 별도 분석이 필요하다.
Modulo
홀수 의 제곱은 항상
이다. 실제로 이면
이고 은 짝수이다.
따라서 홀수 와 에 대해
이다. 해가 존재하면 일반적으로 modulo 에서 네 개의 홀수 root가 생긴다. 홀수 소수의 경우와 달리 derivative 가 modulo 2에서 invertible하지 않기 때문에 lift 구조가 다르다.
General Composite Modulus
로 소인수분해하고 이라 하자. CRT에 의해
이 풀릴 필요충분조건은 각 prime power에 대해
가 모두 풀리는 것이다.
각 홀수 prime power에서 두 root가 있고 부분이 없다면 전체 root의 개수는 이다. CRT는 각 component root의 선택을 독립적으로 결합한다.
예제:
이다. modulo 23과 59에서 각각 root를 구하면
와 같이 두 개씩 존재한다. 네 가지 조합을 CRT로 결합하여 modulo 1357에서 네 root를 얻는다. 이처럼 합성수 법의 해는 각 소수 법의 해 선택을 조합한 것이다.
정리
Hensel lifting은 root를 에서 로 올릴 때 필요한 보정값을 linear congruence로 결정한다. 홀수 소수에서 nonsingular root는 유일하게 lift되며, modulo 에서는 조건이 핵심이다. 일반 합성수 법은 prime power별 해결 후 CRT로 결합한다.
연습 문제
- 의 해를 구한다.
- 의 해 존재 여부를 판정한다.
- 의 모든 해를 구한다.
풀이
1번
modulo 5에서 는 해가 없으므로 modulo 25에서도 해가 없다.
2번
이므로 해가 존재한다. 직접 계산하면 이다.
3번
modulo 3에서 , modulo 5에서도 이다. 네 조합을 CRT로 결합하면
이다.