2차 잉여

 


1. 정의
2. 성질
2.1. 오일러 판정법
2.2. 가우스 판정법
2.3. 가우스의 상호법칙
3. 관련 문서

二次剩餘
'''Quadratic residue.'''

1. 정의

$$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(b,P\right)=1$$인 수 $$b$$에 대하여 야코비 기호 $$\left(\frac{b}{P}\right)=\left(\frac{b}{p_1}\right)\left(\frac{b}{p_2}\right)\cdots\left(\frac{b}{p_m}\right)$$로 정의한다. 야코비 기호에 대해서도 아래의 르장드르 기호의 성질들은 성립하나, $$\left(\frac{b}{P}\right)=1$$이라 해서 $$b$$가 법 $$P$$에 대한 이차 잉여인 것은 아니다.

2. 성질

$$p$$가 홀수인 소수이고, $$a,b$$가 $$p$$와 서로소일 때, 다음이 성립한다.
  1. $$a\equiv b \left(\text{mod}\,p\right)$$이면, $$\displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$$.
  2. $$\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$.
  3. $$\displaystyle \left(\frac{a^2}{p}\right)=1$$.
  4. $$\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right)$$.
  5. $$\displaystyle \left(\frac{1}{p}\right)=1$$.
  6. $$p$$가 홀수인 소수일 때, $$\displaystyle \left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}$$.
  7. $$p$$가 홀수인 소수일 때, p의 완전 잉여계 중에는 $$\frac{p-1}{2}$$개의 2차 잉여와 $$\frac{p-1}{2}$$개의 2차 비잉여가 존재한다.
1~5의 증명:
어려운 증명 없이 르장드르 기호의 정의로 충분히 해결할 수 있다.
6번의 증명:
윌슨의 정리를 이용하면, $$\displaystyle -1\equiv \left(p-1\right)! \equiv 1\times 2\times \cdots \times \frac{p-1}{2} \times \left(p-\frac{p-1}{2}\right) \times \cdots \times \left(p-2\right) \times \left(p-1\right) \equiv \left(1\times 2\times \cdots \times \frac{p-1}{2}\right)^2 (-1)^{\frac{p-1}{2}} \left(\text{mod}\,p\right)$$이므로 $$\displaystyle \left(-1\right)^{\frac{p-1}{2}}=1$$이면 -1은 p의 2차잉여가 된다. 한편 $$\displaystyle \left(-1\right)^{\frac{p-1}{2}}=-1$$이면, $$x^2\equiv -1 \left(\text{mod}\,p\right)$$이라고 할 때 $$x^{p-1}\equiv (-1)^{\frac{p-1}{2}}\equiv -1 \left(\text{mod}\,p\right)$$이므로 페르마 소정리에 모순이다. 따라서 이 경우 -1이 p의 2차잉여가 아니다.
7번의 증명:
임의의 완전잉여계 중에서, $$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$$일 때,
$$\displaystyle \left(\frac{a}{p}\right)\equiv a^{(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)$$를 갖는다.
증명 :
$$x^2\equiv a\left(\text{mod}\,p\right)$$의 해가 존재한다고 하자. 즉, $$\displaystyle \left(\frac{a}{p}\right)= 1$$이라고 하자. 이때 $$\gcd\left(a,p\right)=1$$이므로 $$\gcd\left(x,p\right)=1$$이다.
그러면 페르마의 소정리에 의해 $$x^{p-1}\equiv 1\left(\text{mod}\,p\right)$$이므로, $$\displaystyle a^{(p-1)/2}\equiv x^{p-1}\equiv 1 \left(\text{mod}\,p\right)$$이다. 즉, $$\displaystyle \left(\frac{a}{p}\right)=1\equiv a^{(p-1)/2} \left(\text{mod}\,p\right)$$
반대로, $$\displaystyle a^{(p-1)/2}\equiv 1 \left(\text{mod}\,p\right)$$이라고 하자. 이때 $$r$$를 p의 원시근[1] 이라 하면 $$r^k\equiv a\left(\text{mod}\,p\right)$$인 정수 k가 존재한다. 그러면 $$r^{k(p-1)/2} \equiv a^{(p-1)/2} \equiv 1\left(\text{mod}\,p\right)$$ 이다.
여기서 r이 p의 원시근이므로 $$\displaystyle (p-1)\mid\frac{k(p-1)}{2}$$이어야 하고, $$k$$ 는 짝수가 된다. 즉, $$k=2l$$로 쓸 수 있고, $$\left(r^{l}\right)^2\equiv a\left(\text{mod}\,p\right)$$ 이므로 $$x^2\equiv a\left(\text{mod}\,p\right)$$의 해가 존재한다. 따라서 $$\displaystyle \left(\frac{a}{p}\right)= 1 \equiv a^{(p-1)/2} \left(\text{mod}\,p\right)$$
마찬가지로 $$x^2\equiv a\left(\text{mod}\,p\right)$$의 해가 없는 경우, 즉 $$\displaystyle \left(\frac{a}{p}\right)=-1$$인 경우에 위와 같이 원시근 r를 생각하면 $$r^k\equiv a\left(\text{mod}\,p\right)$$인 k가 홀수여야 한다. 따라서 $$a^{p-1} \equiv 1 \left(\text{mod}\,p\right)$$이 성립하는데 $$a^{(p-1)/2} \equiv 1 \left(\text{mod}\,p\right)$$은 성립할 수 없으므로, $$a^{(p-1)/2} \equiv -1 \left(\text{mod}\,p\right)$$이다.

2.2. 가우스 판정법

$$p$$가 홀수인 소수일 때, 다음이 성립한다.
  • $$\displaystyle \left(\frac{2}{p}\right)=\left(-1\right)^\frac{p^2-1}{8}$$
  • $$\mathrm{gcd}(a, p)=1$$일 때, $$\displaystyle \left(\frac{a}{p}\right)=\left(-1\right)^n$$. 여기서 n은 $$\displaystyle \left\{a, 2a, \cdots, \frac{p-1}{2}a\right\}$$중에서 p로 나눈 나머지가 $$\displaystyle \frac{p}{2}$$보다 큰 것의 개수
  • $$\mathrm{gcd}(a, 2p)=1$$일 때, $$\displaystyle \left(\frac{a}{p}\right)=\left(-1\right)^t$$. 여기서 $$\displaystyle t= \sum_{j=1}^{(p-1)/2} \left\lfloor\frac{ja}{p}\right\rfloor$$.
위 식에서 $$\lfloor\cdot\rfloor$$는 바닥함수를 뜻한다.

2.3. 가우스의 상호법칙

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

3. 관련 문서


[1] 원시근은 법 p에 대한 위수가 $$p-1$$인 것을 말한다. r이 p의 원시근이면 $$ \left\{r, r^2, \cdots, r^{p-1} \right\} \equiv \left\{1, 2, \cdots, p-1 \right\} \left(\text{mod}\,p\right)$$이다. 참고로 법 p에 대한 b의 위수란 $$b^x \equiv 1 \left(\mathrm{mod} p \right)$$인 최소의 정수 x로, $$ \mathrm{ord}_p\left(b\right)$$로 나타낸다.

분류