2차 잉여

분류

정수론

1. 정의2. 성질

2.1. [[오일러]] 판정법2.2. [[가우스]] 판정법2.3. [[가우스]]의 상호법칙

3. 관련 문서

二次剩餘
Quadratic residue.

1. 정의

[math(m)]이 1보다 큰 자연수이고, [math(gcdleft(a,mright)=1)]일 때, 합동식 [math(x^2equiv aleft(text{mod},mright))]이 해를 가지면 [math(a)]를 법 [math(m)]에 관한 2차 잉여(quadratic residue)라 하고, 이 합동식이 해를 갖지 않으면 [math(a)]를 법 [math(m)]에 관한 2차 비잉여(non-quadratic residue)라 한다. [math(p)]가 임의의 홀수인 소수이고, [math(gcdleft(a,pright)=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(gcdleft(b,Pright)=1)]인 수 [math(b)]에 대하여 야코비 기호 [math(left(frac{b}{P}right)=left(frac{b}{p_1}right)left(frac{b}{p_2}right)cdotsleft(frac{b}{p_m}right))]로 정의한다. 야코비 기호에 대해서도 아래의 르장드르 기호의 성질들은 성립하나, [math(left(frac{b}{P}right)=1)]이라 해서 [math(b)]가 법 [math(P)]에 대한 이차 잉여인 것은 아니다.

2. 성질

[math(p)]가 홀수인 소수이고, [math(a,b)]가 [math(p)]와 서로소일 때, 다음이 성립한다.

[math(aequiv b left(text{mod},pright))]이면, [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(-1right)^{frac{p-1}{2}})].
[math(p)]가 홀수인 소수일 때, p의 완전 잉여계 중에는 [math(frac{p-1}{2})]개의 2차 잉여와 [math(frac{p-1}{2})]개의 2차 비잉여가 존재한다.

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

6번의 증명:

윌슨의 정리를 이용하면, [math(displaystyle -1equiv left(p-1right)! equiv 1times 2times cdots times frac{p-1}{2} times left(p-frac{p-1}{2}right) times cdots times left(p-2right) times left(p-1right) equiv left(1times 2times cdots times frac{p-1}{2}right)^2 (-1)^{frac{p-1}{2}} left(text{mod},pright))]이므로 [math(displaystyle left(-1right)^{frac{p-1}{2}}=1)]이면 -1은 p의 2차잉여가 된다. 한편 [math(displaystyle left(-1right)^{frac{p-1}{2}}=-1)]이면, [math(x^2equiv -1 left(text{mod},pright))]이라고 할 때 [math(x^{p-1}equiv (-1)^{frac{p-1}{2}}equiv -1 left(text{mod},pright))]이므로 페르마 소정리에 모순이다. 따라서 이 경우 -1이 p의 2차잉여가 아니다.

7번의 증명:

임의의 완전잉여계 중에서, [math(p)]와 서로소이고, 2차 잉여가 되기 위해서는 [math(1^2,2^2,cdots,left(p-1right)^2)]중 어떤 한 원소와 법 [math(p)]에 의해 같아야 한다. 그런데, [math(left(p-nright)^2equiv left(-nright)^2equiv n^2 left(text{mod},pright))]이므로 그 원소는 [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(gcdleft(a,pright)=1)]일 때,

[math(displaystyle left(frac{a}{p}right)equiv a^{(p-1)/2} left(text{mod},pright))]

이다. 또, [math(a)]가 법 [math(p)]에 관한 2차 잉여이면, 이차합동식 [math(x^2equiv aleft(text{mod},pright))]는 꼭 두 개의 해 [math(xequivpm x_0left(text{mod},pright))]를 갖는다.

증명 :

[math(x^2equiv aleft(text{mod},pright))]의 해가 존재한다고 하자. 즉, [math(displaystyle left(frac{a}{p}right)= 1)]이라고 하자. 이때 [math(gcdleft(a,pright)=1)]이므로 [math(gcdleft(x,pright)=1)]이다.

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

반대로, [math(displaystyle a^{(p-1)/2}equiv 1 left(text{mod},pright))]이라고 하자. 이때 [math(r)]를 p의 원시근[2]인 것을 말한다. r이 p의 원시근이면 [math( left{r, r^2, cdots, r^{p-1} right} equiv left{1, 2, cdots, p-1 right} left(text{mod},pright))]이다. 참고로 법 p에 대한 b의 위수란 [math(b^x equiv 1 left(mathrm{mod} p right))]인 최소의 정수 x로, [math( mathrm{ord}_pleft(bright))]로 나타낸다.] 이라 하면 [math(r^kequiv aleft(text{mod},pright))]인 정수 k가 존재한다. 그러면 [math(r^{k(p-1)/2} equiv a^{(p-1)/2} equiv 1left(text{mod},pright))] 이다.

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

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

2.2. 가우스 판정법

[math(p)]가 홀수인 소수일 때, 다음이 성립한다.

[math(displaystyle left(frac{2}{p}right)=left(-1right)^frac{p^2-1}{8})]
[math(mathrm{gcd}(a, p)=1)]일 때, [math(displaystyle left(frac{a}{p}right)=left(-1right)^n)]. 여기서 n은 [math(displaystyle left{a, 2a, cdots, frac{p-1}{2}aright})]중에서 p로 나눈 나머지가 [math(displaystyle frac{p}{2})]보다 큰 것의 개수
[math(mathrm{gcd}(a, 2p)=1)]일 때, [math(displaystyle left(frac{a}{p}right)=left(-1right)^t)]. 여기서 [math(displaystyle t= sum_{j=1}^{(p-1)/2} leftlfloorfrac{ja}{p}rightrfloor)].

위 식에서 [math(lfloorcdotrfloor)]는 바닥함수를 뜻한다.

2.3. 가우스의 상호법칙

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

3. 관련 문서

[1] 원시근은 법 p에 대한 위수가 [math(p-1)[2] 원시근은 법 p에 대한 위수가 [math(p-1)