나무모에 미러 (일반/밝은 화면)
최근 수정 시각 : 2023-10-14 07:28:47

2차 잉여

정수론
Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"		 공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수·배수 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론(국소체) · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

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

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)]와 서로소일 때, 다음이 성립한다.
  1. [math(a\equiv b \pmod{p})]이면, [math(\displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right))].
  2. [math(\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right))].
  3. [math(\displaystyle \left(\frac{a^2}{p}\right)=1)].
  4. [math(\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right))].
  5. [math(\displaystyle \left(\frac{1}{p}\right)=1)].
  6. [math(p)]가 홀수인 소수일 때, [math(\displaystyle \left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}})].
  7. [math(p)]가 홀수인 소수일 때, p의 완전 잉여계 중에는 [math(\frac{p-1}{2})]개의 2차 잉여와 [math(\frac{p-1}{2})]개의 2차 비잉여가 존재한다.

1~5의 증명:
어려운 증명 없이 르장드르 기호의 정의로 충분히 해결할 수 있다.

6번의 증명:
윌슨의 정리를 이용하면, [math(\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}} \pmod{p})]이므로 [math(\displaystyle \left(-1\right)^{\frac{p-1}{2}}=1)]이면 -1은 p의 2차잉여가 된다. 한편 [math(\displaystyle \left(-1\right)^{\frac{p-1}{2}}=-1)]이면, [math(x^2\equiv -1 \pmod{p})]이라고 할 때 [math(x^{p-1}\equiv (-1)^{\frac{p-1}{2}}\equiv -1 \pmod{p})]이므로 페르마 소정리에 모순이다. 따라서 이 경우 -1이 p의 2차잉여가 아니다.

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

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})]를 갖는다.

증명 :
[math(x^2\equiv a\pmod{p})]의 해가 존재한다고 하자. 즉, [math(\displaystyle \left(\frac{a}{p}\right)= 1)]이라고 하자. 이때 [math(\gcd\left(a,p\right)=1)]이므로 [math(\gcd\left(x,p\right)=1)]이다.

그러면 페르마의 소정리에 의해 [math(x^{p-1}\equiv 1\pmod{p})]이므로, [math(\displaystyle a^{(p-1)/2}\equiv x^{p-1}\equiv 1 \pmod{p})]이다. 즉, [math(\displaystyle \left(\frac{a}{p}\right)=1\equiv a^{(p-1)/2} \pmod{p})]

반대로, [math(\displaystyle a^{(p-1)/2}\equiv 1 \pmod{p})]이라고 하자. 이때 [math(r)]를 p의 원시근[1] 이라 하면 [math(r^k\equiv a\pmod{p})]인 정수 k가 존재한다. 그러면 [math(r^{k(p-1)/2} \equiv a^{(p-1)/2} \equiv 1\pmod{p})] 이다.

여기서 r이 p의 원시근이므로 [math(\displaystyle (p-1)\mid\frac{k(p-1)}{2})]이어야 하고, [math(k)] 는 짝수가 된다. 즉, [math(k=2l)]로 쓸 수 있고, [math(\left(r^{l}\right)^2\equiv a\pmod{p})] 이므로 [math(x^2\equiv a\pmod{p})]의 해가 존재한다. 따라서 [math(\displaystyle \left(\frac{a}{p}\right)= 1 \equiv a^{(p-1)/2} \pmod{p})]

마찬가지로 [math(x^2\equiv a\pmod{p})]의 해가 없는 경우, 즉 [math(\displaystyle \left(\frac{a}{p}\right)=-1)]인 경우에 위와 같이 원시근 r를 생각하면 [math(r^k\equiv a\pmod{p})]인 k가 홀수여야 한다. 따라서 [math(a^{p-1} \equiv 1 \pmod{p})]이 성립하는데 [math(a^{(p-1)/2} \equiv 1 \pmod{p})]은 성립할 수 없으므로, [math(a^{(p-1)/2} \equiv -1 \pmod{p})]이다.

2.2. 가우스 판정법

[math(p)]가 홀수인 소수일 때, 다음이 성립한다.위 식에서 [math(\lfloor\cdot\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. 관련 문서

[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))]로 나타낸다.

분류