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

2차 잉여(Quadratic residue)

m이 1보다 큰 자연수이고, $\gcd\left(a,m\right)=1$일 때, 합동식

$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$\times$QR=QR

2. NR$\times$NR=QR

3. QR$\times$NR=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번이 성립한다.