정의
3 이상의 정수 \(m\)과 \((a,m)=1\)인 정수 \(a\)가 주어졌을 때, 법 \(m\)에 대한 합동식
- [math]\displaystyle{ x^2\equiv a\pmod m }[/math]
의 해가 존재하면 \(a\)를 법 \(m\)에 대한 이차잉여(quadratic residue)라고 한다. 합동식의 해가 존재하지 않으면 \(a\)를 법 \(m\)에 대한 이차비잉여(quadratic nonresidue)라고 한다.
예시
\(m=11\)이라 가정하자. 그럼,
- [math]\displaystyle{ 1^2\equiv\left(-1\right)^2\equiv10^2\equiv1\pmod{11} }[/math]
- [math]\displaystyle{ 2^2\equiv\left(-2\right)^2\equiv9^2\equiv4\pmod{11} }[/math]
- [math]\displaystyle{ 3^2\equiv\left(-3\right)^2\equiv8^2\equiv9\pmod{11} }[/math]
- [math]\displaystyle{ 4^2\equiv\left(-4\right)^2\equiv7^2\equiv5\pmod{11} }[/math]
- [math]\displaystyle{ 5^2\equiv\left(-5\right)^2\equiv6^2\equiv3\pmod{11} }[/math]
이므로, 1, 3, 4, 5, 9는 법 11에 관한 이차잉여가 된다. 2, 6, 7, 8, 10은 법 11에 관한 이차비잉여이다.
여기서 주의깊게 봐야할 점은, 11이 소수라는 것과 정확히 5개의 이차잉여와 5개의 이차비잉여가 있다는 점이다. 이는 모든 소수에대해 성립하며, 증명은 바로 아랫 문단의 성질을 참고하자.
성질
\(p\)는 홀수인 소수, \(a\)는 \(p\)와 서로소인 정수, \(r\)은 \(p\)의 원시근이라 가정하자.
- [math]\displaystyle{ x^2\equiv a\pmod p }[/math]는 근을 가지지 않거나 정확히 두 개의 근을 가진다.
- 주어진 합동식이 근을 가지지 않으면 명제는 자연히 참이다. 만약 \(x_0\)이 주어진 합동식의 한 근이라면, \(-x_0\)도 근이 된다. 또한, \(p\)는 홀수이므로, [math]\displaystyle{ x_0\equiv-x_0\pmod p }[/math] (기우성이 다르다). 이제 \(y\)가 합동식의 또다른 근이라고 가정하자. 그럼 [math]\displaystyle{ y^2\equiv a\equiv {x_0}^2\equiv p }[/math]이고, [math]\displaystyle{ \left(y-x_0\right)\left(y+x_0\right)\equiv0\pmod p }[/math]이다. 이는 곧 [math]\displaystyle{ p\mid\left(y-x_0\right)\left(y+x_0\right) }[/math]임을 의미하고, \(p\)가 소수이므로 [math]\displaystyle{ p\mid y-x_0 }[/math] 혹은 [math]\displaystyle{ p\mid y+x_0 }[/math]이다. 어느쪽이든, [math]\displaystyle{ y\equiv\pm x_0\pmod p }[/math]이다. 즉, 주어진 합동식은 정확히 두 개의 근만을 가진다.
- 법 \(p\)에 대해 정확히 [math]\displaystyle{ \frac{p-1}{2} }[/math]개의 이차잉여와 이차비잉여가 존재한다.
- 바로 위 성질의 따름정리. 증명은 생략.
- \(a\)가 법 \(p\)에 대한 이차잉여라면, [math]\displaystyle{ \operatorname{ind}_ra }[/math]는 짝수이다. 역도 성립한다.
- [math]\displaystyle{ \operatorname{ind}_ra }[/math]가 짝수라 가정하자. 그럼, [math]\displaystyle{ a\equiv r^{\operatorname{ind}_ra}\equiv r^{\left(\frac{\operatorname{ind}_ra}{2}\right)2}\equiv\left(r^{\frac{\operatorname{ind}_ra}{2}}\right)^2\pmod p }[/math]이다. 따라서, \(a\) 는 법 \(p\)에 대한 이차잉여이다. 역으로, [math]\displaystyle{ x^2\equiv a\pmod p }[/math]의 해가 존재한다고 가정하자. 그럼, 한 해 \(x_0\)에 대해 [math]\displaystyle{ {x_0}^2\equiv a\pmod p }[/math]이고, 양변에 이산로그를 씌우면 [math]\displaystyle{ 2\operatorname{ind}_r{x_0}\equiv\operatorname{ind}_ra\pmod{p-1} }[/math]이다. 따라서, 적당한 정수 \(k\)에 대해 [math]\displaystyle{ \operatorname{ind}_ra=2\operatorname{ind}_r{x_0}+k\left(p-1\right) }[/math]이고, \(p-1\)은 짝수이므로 [math]\displaystyle{ \operatorname{ind}_ra }[/math]도 짝수이다.
- 원시근은 이차비잉여이다.
- [math]\displaystyle{ \operatorname{ind}_rr=1 }[/math]은 홀수이므로 위 성질에 의해 \(r\)은 이차비잉여이다.
르장드르 기호를 사용하면 더 많은 성질을 알 수 있다. 르장드르 기호에 관련된 것은 항목 참조.
이차 합동방정식
[math]\displaystyle{ ax^2+bx+c\equiv0\pmod m }[/math]의 형태를 가진 합동식을 이차 합동방정식이라 부른다. 일차 합동식과는 달리 이차 합동식은 푸는 것이 까다롭기 때문에 여기서는 간단한 형태의 합동식만 풀어보도록 하자.
여기서 \(p\)는 소수이다. 만약 [math]\displaystyle{ p=2 }[/math]라면, 가능한 \(x\)값이 0, 1 두 개밖에 없으므로 직접 넣어서 확인하는 것이 제일 빠르다. 아니면 \(a\)와 \(x\)의 기우성이 같다는 사실을 이용해도 된다. 해는 반드시 유일하게 존재하게 된다.
만약 \(p\)가 홀수인 소수라면, \(a\)의 값에 따라 해가 존재할 수도 있고, 없을 수도 있다. 해가 존재하기 위한 조건은 \(\left(\frac{a}{p}\right)=1\)인 것 (르장드르 기호 참조). 만약 \(\left(\frac{a}{p}\right)=-1\)라면 해는 존재하지 않는다. \(\left(\frac{a}{p}\right)\)값을 구하는 방법은 르장드르 기호 항목에 여러가지가 있으니 그쪽을 참조하자. 해가 존재함을 밝혀냈다면, 위 성질의 1번에 의해 서로다른 두 개의 해가 존재함을 알 수 있다. 한 해를 \(x_0\)라 하면, 다른 해는 자연히 \(-x_0\). 문제는 해인 \(x_0\)를 찾는 것인데, 알려진 방법이 노가다밖에 없다. \(x\)를 찾기 위해서는 이산로그를 사용해야 하는데, 이산로그 값을 찾는 일반적인 방법은 알려지지 않았기 때문. 물론, \(a\)가 완전제곱수같은 특수한 경우라면 해를 금방 찾을 수 있다. 다른 경우는 바로 [math]\displaystyle{ p\equiv3\pmod4 }[/math]인 경우. 이 경우엔 [math]\displaystyle{ a^{\frac{p+1}{4}} }[/math]가 한 해가 된다. 오일러 판정법에 의해 [math]\displaystyle{ x^2\equiv a^{\frac{p+1}{2}}\equiv a^{\frac{p-1}{2}}a\equiv\left(\frac{a}{p}\right)a\equiv a\pmod p }[/math]이기 때문.
여기서 \(p,\,q\)는 서로다른 두 소수이다. 이제, [math]\displaystyle{ \gcd\left(a,pq\right)=1 }[/math]이고, 합동식의 해가 존재한다고 가정하자. \(x_0\)가 한 해라면, [math]\displaystyle{ {x_0}^2\equiv a\pmod p }[/math]이고 [math]\displaystyle{ {x_0}^2\equiv a\pmod q }[/math]이다. 만약 [math]\displaystyle{ \left(\frac{a}{p}\right)=-1 }[/math]이거나 [math]\displaystyle{ \left(\frac{a}{q}\right)=-1 }[/math]라면, 두 개로 쪼갠 합동식 중 하나는 해가 존재하지 않으므로 원래 합동식의 해도 존재하지 않게 된다. 따라서, [math]\displaystyle{ \left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=1 }[/math]이라고 가정하자. 첫 번째 합동식의 해를 \(\pm x_1\), 두 번째 합동식의 해를 \(\pm x_2\)라 하면, 우리가 풀고자 하는 원래 합동식은,
- [math]\displaystyle{ \begin{cases}x&\equiv x_1\pmod p\\x&\equiv x_2\pmod q\end{cases}\quad\begin{cases}x&\equiv -x_1\pmod p\\x&\equiv x_2\pmod q\end{cases}\quad\begin{cases}x&\equiv x_1\pmod p\\x&\equiv -x_2\pmod q\end{cases}\quad\begin{cases}x&\equiv -x_1\pmod p\\x&\equiv -x_2\pmod q\end{cases} }[/math]
의 네 연립 일차 합동식과 동치이다. 그런데 \(p\)와 \(q\)는 서로소이므로, 중국인의 나머지 정리에 의해 위의 각 연립 일차 합동식은 법 \(pq\)에 대해 해가 유일하게 존재함을 알 수 있다. 따라서, [math]\displaystyle{ x^2\equiv a\pmod{pq} }[/math]의 해가 존재한다면, 그 해는 총 네 개이다.
만약 [math]\displaystyle{ p_1,\,p_2,\,\ldots,\,p_k }[/math]가 서로다른 소수라면, 위에서 했던 방법과 같은 방법으로 이차 합동식을 풀 수 있다. 해의 개수는 총 [math]\displaystyle{ 2^k }[/math]개.