2차 잉여
덤프버전 :
분류
1. 개요[편집]
二次剩餘 / quadratic residue
[math(m)]이 1보다 큰 자연수이고, [math(\gcd\left(a,m\right)=1)]일 때, 합동식 [math(x^2\equiv a\pmod{m})]이 해를 가지면 [math(a)]를 법 [math(m)]에 관한 2차 잉여(quadratic residue)라 하고, 이 합동식이 해를 갖지 않으면 [math(a)]를 법 [math(m)]에 관한 2차 비잉여(non-quadratic residue)라 한다. [math(p)]가 임의의 홀수인 소수이고, [math(\gcd\left(a,p\right)=1)]일 때 [math(a)]가 법 [math(p)]에 관한 2차 잉여이면 [math(\left(\frac{a}{p}\right)=1)]로 표시하고, 그렇지 않으면 [math(\left(\frac{a}{p}\right)=-1)]로 표시한다. 이 때, [math(\left(\frac{a}{p}\right))]를 르장드르 기호(Legendre symbol)라 한다.
이것을 일반화한 것으로 야코비 기호가 있다. 1보다 큰 홀수 [math(P)]에 대하여 [math(P=p_1 p_2 \cdots p_m)]이 성립한다고 하자. 단, [math(p_1,p_2,\cdots,p_m)]는 홀수인 소수이며, 이 중에는 같은 것이 있을 수 있다. 이때, [math(\gcd\left(b,P\right)=1)]인 수 [math(b)]에 대하여 야코비 기호 [math(\left(\frac{b}{P}\right)=\left(\frac{b}{p_1}\right)\left(\frac{b}{p_2}\right)\cdots\left(\frac{b}{p_m}\right))]로 정의한다. 야코비 기호에 대해서도 아래의 르장드르 기호의 성질들은 성립하나, [math(\left(\frac{b}{P}\right)=1)]이라 해서 [math(b)]가 법 [math(P)]에 대한 이차 잉여인 것은 아니다. 다만, 홀수 소수 [math(p)]에 대하여 야코비 기호 [math(\displaystyle \left(\frac{a}{p}\right))]는 르장드르 기호와 계산값이 완벽하게 일치하며, 이를 이용하여 르장드르 기호의 계산을 할 수 있다.
2. 성질[편집]
[math(p)]가 홀수인 소수이고, [math(a,b)]가 [math(p)]와 서로소일 때, 다음이 성립한다.
- [math(a\equiv b \pmod{p})]이면, [math(\displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right))].
- [math(\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right))].
- [math(\displaystyle \left(\frac{a^2}{p}\right)=1)].
- [math(\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right))].
- [math(\displaystyle \left(\frac{1}{p}\right)=1)].
- [math(p)]가 홀수인 소수일 때, [math(\displaystyle \left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}})].
- [math(p)]가 홀수인 소수일 때, p의 완전 잉여계 중에는 [math(\frac{p-1}{2})]개의 2차 잉여와 [math(\frac{p-1}{2})]개의 2차 비잉여가 존재한다.
1~5의 증명:
어려운 증명 없이 르장드르 기호의 정의로 충분히 해결할 수 있다.
6번의 증명:
7번의 증명:
2.1. 오일러 판정법[편집]
[math(p)]가 홀수인 소수이고, [math(\gcd\left(a,p\right)=1)]일 때,
[math(\displaystyle \left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \pmod{p})]
이다. 또, [math(a)]가 법 [math(p)]에 관한 2차 잉여이면, 이차합동식 [math(x^2\equiv a\pmod{p})]는 꼭 두 개의 해 [math(x\equiv\pm x_0\pmod{p})]를 갖는다.증명 :
2.2. 가우스 판정법[편집]
[math(p)]가 홀수인 소수일 때, 다음이 성립한다.
- [math(\displaystyle \left(\frac{2}{p}\right)=\left(-1\right)^\frac{p^2-1}{8})]
- [math(\mathrm{gcd}(a, p)=1)]일 때, [math(\displaystyle \left(\frac{a}{p}\right)=\left(-1\right)^n)]. 여기서 n은 [math(\displaystyle \left\{a, 2a, \cdots, \frac{p-1}{2}a\right\})]중에서 p로 나눈 나머지가 [math(\displaystyle \frac{p}{2})]보다 큰 것의 개수
- [math(\mathrm{gcd}(a, 2p)=1)]일 때, [math(\displaystyle \left(\frac{a}{p}\right)=\left(-1\right)^t)]. 여기서 [math(\displaystyle t= \sum_{j=1}^{(p-1)/2} \left\lfloor\frac{ja}{p}\right\rfloor)].
2.3. 가우스의 상호법칙[편집]
[math(p,q)]가 서로 다른 홀수인 소수일 때, [math(\displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}})]이다.
3. 관련 문서[편집]
이 문서의 내용 중 전체 또는 일부는 2023-10-18 12:46:41에 나무위키 2차 잉여 문서에서 가져왔습니다.
[1] 원시근은 법 p에 대한 위수가 [math(p-1)]인 것을 말한다. r이 p의 원시근이면 [math( \left\{r, r^2, \cdots, r^{p-1} \right\} \equiv \left\{1, 2, \cdots, p-1 \right\} \pmod{p})]이다. 참고로 법 p에 대한 b의 위수란 [math(b^x \equiv 1 \pmod{p})]인 최소의 정수 x로, [math( \mathrm{ord}_p\left(b\right))]로 나타낸다.