2차 잉여

• 상위 항목: 수학 관련 정보, 정수론

quadratic residue. 2차 잉여 풀어드렸습니다.

1 개요

평범한 사람들은 평생 볼 일이 없는 개념이지만, 대학에서 수학을 전공하거나 KMO같은 수학 경시대회를 준비한다면 보게 될 개념 중 하나. 자세한 정의는 다음과 같다.

$$m$$ 이 1보다 큰 자연수이고, $$\gcd\left(a,m\right)=1$$ 일 때, 합동식 $$x^2\equiv a\left(\text{mod}\,m\right)$$ 이 해를 가지면 $$a$$ 를 법 $$m$$ 에 관한 2차 잉여(quadratic residue)라 하고, 이 합동식이 해를 갖지 않으면 $$a$$ 를 법 $$m$$ 에 관한 2차 비잉여(non-quadratic residue)라 한다. $$p$$ 가 임의의 홀수인 소수이고, $$\gcd\left(a,p\right)=1$$ 일 때 $$a$$ 가 법 $$p$$ 에 관한 2차 잉여이면 $$\left(\frac{a}{p}\right)=1$$ 로 표시하고, 그렇지 않으면 $$\left(\frac{a}{p}\right)=-1$$ 로 표시한다. 이 때, $$\left(\frac{a}{p}\right)$$ 를 르장드르 기호(Legendre symbol)라 한다.
또한, 1보다 큰 홀수 $$p$$ 에 대하여 $$p=p_1 p_2 \cdots p_m$$ 이 성립한다고 하자. 단, $$p_1,p_2,\cdots,p_m$$ 는 홀수인 소수이며, 이 중에는 같은 것이 있을 수 있다. 이때, $$\gcd\left(a,p\right)=1$$ 인 정수 $$a$$ 에 대하여 $$\left(\frac{a}{p}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_m}\right)$$ 로 정의한다.

2 성질

$$p$$ 가 홀수인 소수이고, $$a,b$$ 가 $$p$$ 와 서로소일 때, 다음이 성립한다.

1. $$a\equiv b \left(\text{mod}\,p\right)$$ 이면, $$\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$$ 이다.
2. $$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$ 이다.
3. $$\left(\frac{a^2}{p}\right)=1$$ 이다.
4. $$\left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right)$$ 이다.
5. $$\left(\frac{1}{p}\right)=1$$ 이다.
6. $$p$$ 가 홀수인 소수일 때, 합동식 $$x^2\equiv -1\left(\text{mod}\,p\right)$$ 가 해를 가지기 위한 필요충분조건은 $$p\equiv 1\left(\text{mod}\,4\right)$$ 이다.
7. 홀수인 소수 $$p$$ 와 $$\gcd\left(a,p\right)=1$$ 인 정수 $$a$$ 에 대하여 $$a$$ 가 법 $$p$$ 에 대한 2차 잉여일 필요충분 조건, 즉 이차 합동식 $$x^2\equiv a\left(\text{mod}\,p\right)$$ 가 해를 가질 필요충분조건은 $$\left(\frac{a}{p}\right)=1$$ 이다.
8. $$p$$ 가 홀수인 소수일 때, 임의의 완전 잉여계 중에는 $$\frac{p-1}{2}$$ 개의 2차 잉여와 $$\frac{p-1}{2}$$ 개의 2차 비잉여가 존재한다.

1~7의 증명:
어려운 증명 없이 르장드르 기호의 정의로 충분히 해결할 수 있다.증명은 독자들에게 연습문제로 남긴다.
8번의 증명:

임의의 완전 잉여계 중에서, $$p$$ 와 서로소이고, 2차 잉여가 되기 위해서는 $$1^2,2^2,\cdots,\left(p-1\right)^2$$ 중 어떤 한 원소와 법 $$p$$ 에 의해 같아야 한다. 그런데, $$\left(p-n\right)^2\equiv \left(-n\right)^2\equiv n^2 \left(\text{mod}\,p\right)$$ 이므로 그 원소는 $$1^2,2^2,\cdots,\left(\frac{p-1}{2}\right)^2$$ 중 한 원소와 법 $$p$$ 에 의해 같아야 한다. 한편, $$1^2,2^2,\cdots,\left(\frac{p-1}{2}\right)^2$$ 은 법 $$p$$ 에 의해 각기 다르므로, 2차 잉여는 $$\frac{p-1}{2}$$ 개이다. 따라서, 2차 비잉여도 $$p-1-\frac{p-1}{2}=\frac{p-1}{2}$$ 개이다.

2.1 오일러 판정법

$$p$$ 가 홀수인 소수이고, $$\gcd\left(a,p\right)=1$$ 일 때,
$$\left(\frac{a}{p}\right)\equiv a^\frac{p-1}{2} \left(\text{mod}\,p\right)$$
이다. 또, $$a$$ 가 법 $$p$$ 에 관한 2차 잉여이면, 이차합동식 $$x^2\equiv a\left(\text{mod}\,p\right)$$ 는 꼭 두 개의 해 $$x\equiv\pm x_0\left(\text{mod}\,p\right)$$ 를 갖는다.

2.2 가우스 판정법

$$p$$ 가 홀수인 소수일 때, $$\left(\frac{2}{p}\right)=\left(-1\right)^\frac{p^2-1}{8}$$ 이다.

2.3 가우스의 상호법칙

$$p,q$$ 가 서로 다른 홀수인 소수일 때, $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$$ 이다.

3 관련 항목

• 합동식
• 완전잉여계
• 기약잉여계