quadratic residue. 2차 잉여 풀어드렸습니다.
1 개요
평범한 사람들은 평생 볼 일이 없는 개념이지만, 대학에서 수학을 전공하거나 KMO같은 수학 경시대회를 준비한다면 보게 될 개념 중 하나. 자세한 정의는 다음과 같다.
[math]m[/math]이 1보다 큰 자연수이고, [math]\gcd\left(a,m\right)=1[/math]일 때, 합동식 [math]x^2\equiv a\left(\text{mod}\,m\right)[/math]이 해를 가지면 [math]a[/math]를 법 [math]m[/math]에 관한 2차 잉여(quadratic residue)라 하고, 이 합동식이 해를 갖지 않으면 [math]a[/math]를 법 [math]m[/math]에 관한 2차 비잉여(non-quadratic residue)라 한다. [math]p[/math]가 임의의 홀수인 소수이고, [math]\gcd\left(a,p\right)=1[/math]일 때 [math]a[/math]가 법 [math]p[/math]에 관한 2차 잉여이면 [math]\left(\frac{a}{p}\right)=1[/math]로 표시하고, 그렇지 않으면 [math]\left(\frac{a}{p}\right)=-1[/math]로 표시한다. 이 때, [math]\left(\frac{a}{p}\right)[/math]를 르장드르 기호(Legendre symbol)라 한다.
또한, 1보다 큰 홀수 [math]p[/math]에 대하여 [math]p=p_1 p_2 \cdots p_m[/math]이 성립한다고 하자. 단, [math]p_1,p_2,\cdots,p_m[/math]는 홀수인 소수이며, 이 중에는 같은 것이 있을 수 있다. 이때, [math]\gcd\left(a,p\right)=1[/math]인 정수 [math]a[/math]에 대하여 [math]\left(\frac{a}{p}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_m}\right)[/math]로 정의한다.
2 성질
[math]p[/math]가 홀수인 소수이고, [math]a,b[/math]가 [math]p[/math]와 서로소일 때, 다음이 성립한다.
- [math]a\equiv b \left(\text{mod}\,p\right)[/math]이면, [math]\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)[/math]이다.
- [math]\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)[/math]이다.
- [math]\left(\frac{a^2}{p}\right)=1[/math]이다.
- [math]\left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right)[/math]이다.
- [math]\left(\frac{1}{p}\right)=1[/math]이다.
- [math]p[/math]가 홀수인 소수일 때, 합동식 [math]x^2\equiv -1\left(\text{mod}\,p\right)[/math]가 해를 가지기 위한 필요충분조건은 [math]p\equiv 1\left(\text{mod}\,4\right)[/math]이다.
- 홀수인 소수 [math]p[/math]와 [math]\gcd\left(a,p\right)=1[/math]인 정수 [math]a[/math]에 대하여 [math]a[/math]가 법 [math]p[/math]에 대한 2차 잉여일 필요충분 조건, 즉 이차 합동식 [math]x^2\equiv a\left(\text{mod}\,p\right)[/math]가 해를 가질 필요충분조건은 [math]\left(\frac{a}{p}\right)=1[/math]이다.
- [math]p[/math]가 홀수인 소수일 때, 임의의 완전 잉여계 중에는 [math]\frac{p-1}{2}[/math]개의 2차 잉여와 [math]\frac{p-1}{2}[/math]개의 2차 비잉여가 존재한다.
1~7의 증명:
어려운 증명 없이 르장드르 기호의 정의로 충분히 해결할 수 있다.증명은 독자들에게 연습문제로 남긴다.
8번의 증명:
임의의 완전 잉여계 중에서, [math]p[/math]와 서로소이고, 2차 잉여가 되기 위해서는 [math]1^2,2^2,\cdots,\left(p-1\right)^2[/math]중 어떤 한 원소와 법 [math]p[/math]에 의해 같아야 한다. 그런데, [math]\left(p-n\right)^2\equiv \left(-n\right)^2\equiv n^2 \left(\text{mod}\,p\right)[/math]이므로 그 원소는 [math]1^2,2^2,\cdots,\left(\frac{p-1}{2}\right)^2[/math] 중 한 원소와 법 [math]p[/math]에 의해 같아야 한다. 한편, [math]1^2,2^2,\cdots,\left(\frac{p-1}{2}\right)^2[/math]은 법 [math]p[/math]에 의해 각기 다르므로, 2차 잉여는 [math]\frac{p-1}{2}[/math]개이다. 따라서, 2차 비잉여도 [math]p-1-\frac{p-1}{2}=\frac{p-1}{2}[/math]개이다.
2.1 오일러 판정법
[math]p[/math]가 홀수인 소수이고, [math]\gcd\left(a,p\right)=1[/math]일 때,
[math]\left(\frac{a}{p}\right)\equiv a^\frac{p-1}{2} \left(\text{mod}\,p\right)[/math]
이다. 또, [math]a[/math]가 법 [math]p[/math]에 관한 2차 잉여이면, 이차합동식 [math]x^2\equiv a\left(\text{mod}\,p\right)[/math]는 꼭 두 개의 해 [math]x\equiv\pm x_0\left(\text{mod}\,p\right)[/math]를 갖는다.
2.2 가우스 판정법
[math]p[/math]가 홀수인 소수일 때, [math]\left(\frac{2}{p}\right)=\left(-1\right)^\frac{p^2-1}{8}[/math]이다.
2.3 가우스의 상호법칙
[math]p,q[/math]가 서로 다른 홀수인 소수일 때, [math]\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}[/math]이다.