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 |