Processing math: 0%

2차 잉여의 성질 & 오일러 판정법

2021. 1. 29. 18:46수학

2차 잉여(Quadratic residue)

이 1보다 큰 자연수이고, gcd일 때, 합동식

x^2 \equiv a (mod\ m)

이 해를 가지면 a를 법 m에 관한 2차 잉여(quadratic residue)라 하고,

이 합동식이 해를 갖지 않으면 a를 법 m에 관한 2차 비잉여(non-quadratic residue)라 한다.

2차 잉여를 QR 2차 비잉여를 NR 이라고 하자.


2차 잉여의 성질 (1)

QR

gcd(x,p)=1인 임의의 x와 임의의 홀수인 소수 p에 대해 다음이 성립한다고 하자.

x^{2} \equiv c (mod\ p) \cdot\cdot\cdot *

페르마의 소정리에 의해

x \equiv \frac{c}{x} \equiv c \cdot x^{p-2} (mod\ p)

*에 의해

x \equiv xc^{\frac{p-1}{2}} (mod\ p)

c^{\frac{p-1}{2}} \equiv 1 (mod\ p)

이떄 c가 QR이라는 것에 주목하자.

 

NR

임의의 NR인 정수 y, \gcd(a,p)=1를 정의하자.

y^{p-1} \equiv 1 (mod\ p)

y^{\frac{p-1}{2}} \equiv \pm1 (mod\ p)

QR 일 때 1와 법 p에 대해 합동이므로 NR 일 경우 

y^{\frac{p-1}{2}} \equiv -1 (mod\ p)

가 성립한다.

 

르장드르 기호

p와 서로소인 임의의 정수 x,y를 정의하자.

이를 르장드르 기호를 통해 나타내면 x, y에 대해

x^{\frac{p-1}{2}} \equiv \left(\frac{x}{p}\right) (mod\ p)

y^{\frac{p-1}{2}} \equiv \left(\frac{y}{p}\right) (mod\ p)

합동식의 곱 성질에 의하여

(xy)^{\frac{p-1}{2}} \equiv \left(\frac{xy}{p}\right) (mod\ p)

이므로 르장드르 기호는 곱셈적 정질을 가진다.

 


2차 잉여의 성질 (2)

증명한 것을 바탕으로

1. QR\timesQR=QR

2. NR\timesNR=QR

3. QR\timesNR=NR

임을 쉽게 보일 수 있다.

 

\left(\frac{x}{p}\right)\cdot\left(\frac{y}{p}\right) =\left(\frac{xy}{p}\right)

 

x, y가 각각 QR이면

1\times1=1

따라서 1번이 성립한다.

 

x, y가 각각 NR이면

(-1)\times(-1)=1

따라서 2번이 성립한다.

 

x, y가 각각 QR, NR이면

1\times(-1)=-1

따라서 3번이 성립한다.

 

'수학' 카테고리의 다른 글

피보나치 수열  (1) 2021.02.15
조합(Combination)  (0) 2021.01.31
윌슨의 정리  (0) 2021.01.29
절댓값 합 함수(Ⅱ)  (3) 2021.01.26
절댓값 합 함수(Ⅰ)  (0) 2021.01.26