정의[편집 | 원본 편집]
3 이상의 정수 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ (a,m)=1 }[/math]인 정수 [math]\displaystyle{ a }[/math]가 주어졌을 때, 법 [math]\displaystyle{ m }[/math]에 대한 합동식
- [math]\displaystyle{ x^2\equiv a\pmod m }[/math]
의 해가 존재하면 [math]\displaystyle{ a }[/math]를 법 [math]\displaystyle{ m }[/math]에 대한 이차잉여(quadratic residue)라고 한다. 합동식의 해가 존재하지 않으면 [math]\displaystyle{ a }[/math]를 법 [math]\displaystyle{ m }[/math]에 대한 이차비잉여(quadratic nonresidue)라고 한다.
예시[편집 | 원본 편집]
[math]\displaystyle{ m=11 }[/math]이라 가정하자. 그럼,
- [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개의 이차비잉여가 있다는 점이다. 이는 모든 소수에대해 성립하며, 증명은 바로 아랫 문단의 성질을 참고하자.
성질[편집 | 원본 편집]
[math]\displaystyle{ p }[/math]는 홀수인 소수, [math]\displaystyle{ a }[/math]는 [math]\displaystyle{ p }[/math]와 서로소인 정수, [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ p }[/math]의 원시근이라 가정하자.
- [math]\displaystyle{ x^2\equiv a\pmod p }[/math]는 근을 가지지 않거나 정확히 두 개의 근을 가진다.
- 주어진 합동식이 근을 가지지 않으면 명제는 자연히 참이다. 만약 [math]\displaystyle{ x_0 }[/math]이 주어진 합동식의 한 근이라면, [math]\displaystyle{ -x_0 }[/math]도 근이 된다. 또한, [math]\displaystyle{ p }[/math]는 홀수이므로, [math]\displaystyle{ x_0\equiv-x_0\pmod p }[/math] (기우성이 다르다). 이제 [math]\displaystyle{ y }[/math]가 합동식의 또다른 근이라고 가정하자. 그럼 [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]임을 의미하고, [math]\displaystyle{ p }[/math]가 소수이므로 [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]이다. 즉, 주어진 합동식은 정확히 두 개의 근만을 가진다.
- 법 [math]\displaystyle{ p }[/math]에 대해 정확히 [math]\displaystyle{ \frac{p-1}{2} }[/math]개의 이차잉여와 이차비잉여가 존재한다.
- 바로 위 성질의 따름정리. 증명은 생략.
- [math]\displaystyle{ a }[/math]가 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여라면, [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]이다. 따라서, [math]\displaystyle{ a }[/math] 는 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여이다. 역으로, [math]\displaystyle{ x^2\equiv a\pmod p }[/math]의 해가 존재한다고 가정하자. 그럼, 한 해 [math]\displaystyle{ x_0 }[/math]에 대해 [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]이다. 따라서, 적당한 정수 [math]\displaystyle{ k }[/math]에 대해 [math]\displaystyle{ \operatorname{ind}_ra=2\operatorname{ind}_r{x_0}+k\left(p-1\right) }[/math]이고, [math]\displaystyle{ p-1 }[/math]은 짝수이므로 [math]\displaystyle{ \operatorname{ind}_ra }[/math]도 짝수이다.
- 원시근은 이차비잉여이다.
- [math]\displaystyle{ \operatorname{ind}_rr=1 }[/math]은 홀수이므로 위 성질에 의해 [math]\displaystyle{ r }[/math]은 이차비잉여이다.
르장드르 기호를 사용하면 더 많은 성질을 알 수 있다. 르장드르 기호에 관련된 것은 항목 참조.
이차 합동방정식[편집 | 원본 편집]
이와 관련한 내용은 모듈러 제곱근에서 볼 수 있습니다.[math]\displaystyle{ ax^2+bx+c\equiv0\pmod m }[/math]의 형태를 가진 합동식을 이차 합동방정식이라 부른다. 일반적인 이차 합동방정식은 통상 이차방정식과 같이 완전제곱식 형태로 묶어서 변형할 수 있다. 주어진 식에서 양 변에 [math]\displaystyle{ 4a }[/math]를 곱하면 [math]\displaystyle{ 4a^2x^2+4abx+4ac \equiv 0 \pmod{4am} }[/math]이고, 이는 [math]\displaystyle{ (2ax+b)^2 \equiv b^2-4ac \pmod{4am} }[/math]으로 쓸 수 있다. 그러므로 주요 관심사는 간단한 형태인 [math]\displaystyle{ x^2 \equiv a \pmod m }[/math]의 해를 구하는 것이며, 자세한 방법은 모듈러 제곱근 문서에 있다. 아래는 그 중 간단한 경우를 다룬다.
여기서 [math]\displaystyle{ p }[/math]는 소수이다. 만약 [math]\displaystyle{ p=2 }[/math]라면, 가능한 [math]\displaystyle{ x }[/math]값이 0, 1 두 개밖에 없으므로 직접 넣어서 확인하는 것이 제일 빠르다. 아니면 [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ x }[/math]의 기우성이 같다는 사실을 이용해도 된다. 해는 반드시 유일하게 존재하게 된다.
만약 [math]\displaystyle{ p }[/math]가 홀수인 소수라면, [math]\displaystyle{ a }[/math]의 값에 따라 해가 존재할 수도 있고, 없을 수도 있다. 해가 존재하기 위한 조건은 [math]\displaystyle{ \left(\frac{a}{p}\right)=1 }[/math]인 것 (르장드르 기호 참조). 만약 [math]\displaystyle{ \left(\frac{a}{p}\right)=-1 }[/math]라면 해는 존재하지 않는다. [math]\displaystyle{ \left(\frac{a}{p}\right) }[/math]값을 구하는 방법은 르장드르 기호 항목에 여러 가지가 있으니 그쪽을 참조하자. 해가 존재함을 밝혀냈다면, 위 성질의 1번에 의해 서로다른 두 개의 해가 존재함을 알 수 있다. 한 해를 [math]\displaystyle{ x_0 }[/math]라 하면, 다른 해는 자연히 [math]\displaystyle{ -x_0 }[/math]. 문제는 해인 [math]\displaystyle{ x_0 }[/math]를 찾는 것인데, 이산로그인 [math]\displaystyle{ \operatorname{ind}_p a }[/math]를 구하거나 토넬리-섕크스 알고리즘을 이용하면 해를 구할 수 있다.
특수한 경우로 [math]\displaystyle{ a }[/math]가 완전제곱수이면 해를 금방 찾을 수 있다. 다른 경우는 바로 [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]이기 때문.
여기서 [math]\displaystyle{ p,\,q }[/math]는 서로다른 두 소수이다. 이제, [math]\displaystyle{ \gcd\left(a,pq\right)=1 }[/math]이고, 합동식의 해가 존재한다고 가정하자. [math]\displaystyle{ x_0 }[/math]가 한 해라면, [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]이라고 가정하자. 첫 번째 합동식의 해를 [math]\displaystyle{ \pm x_1 }[/math], 두 번째 합동식의 해를 [math]\displaystyle{ \pm x_2 }[/math]라 하면, 우리가 풀고자 하는 원래 합동식은,
- [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]
의 네 연립 일차 합동식과 동치이다. 그런데 [math]\displaystyle{ p }[/math]와 [math]\displaystyle{ q }[/math]는 서로소이므로, 중국인의 나머지 정리에 의해 위의 각 연립 일차 합동식은 법 [math]\displaystyle{ pq }[/math]에 대해 해가 유일하게 존재함을 알 수 있다. 따라서, [math]\displaystyle{ x^2\equiv a\pmod{pq} }[/math]의 해가 존재한다면, 그 해는 총 네 개이다.
만약 [math]\displaystyle{ p_1,\,p_2,\,\ldots,\,p_k }[/math]가 서로다른 소수라면, 위에서 했던 방법과 같은 방법으로 이차 합동식을 풀 수 있다. 해의 개수는 총 [math]\displaystyle{ 2^k }[/math]개.