📂정수론

오일러 판정법

정리 ¹

소수 $p \ne 2$ 에 대해 $$ a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p} $$

설명

이에 따르면 $a$ 하나만 이차잉여인지 비이차잉여인지 보고싶을 땐 무작정 계산해보면 그만이다. 물론 거듭제곱이 그렇게 만만한 작업은 아니지만 모든 수를 계산해보는 것보단 나을 것이다. 증명 자체는 별로 어렵지 않지만 보조정리가 많이 쓰이기 때문에 어느정도 공부를 해둬야 이해하기 쉽다.

증명

$a$ 가 QR인 경우와 NR인 경우로 나누어서 살펴보자.

Case 1. $a$가 QR인 경우

$a$가 QR이므로 어떤 $b$ 에 대해 $a = b^2$ 이고 다음이 성립한다. $$ a^{p-1 \over 2} \equiv b^2{p-1 \over 2} \equiv b^{p-1} \pmod{p} $$

페르마의 소정리: $a^{p-1} \equiv 1 \pmod{p}$

페르마의 소정리에 의해 $b^{p-1} \equiv 1 \pmod{p}$ 이므로 $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv 1 \pmod{p} $$

---

Case 2. $a$가 NR인 경우

합동방정식 $x^{p-1} - 1 \equiv 0 \pmod{p}$ 에서 시작한다.

합동방정식에 대한 대수학의 기본정리: $f(x)=a_{ 0 }x^{ d }+a_{ 1 }x^{ d-1 }+ \cdots +a_{ d-1 }x+a_{ d }$ 에 대해 방정식 $f(x)\equiv 0 \pmod{p}$ 은 많아도 $d$ 개의 합동이 아닌 해를 가진다

대수학의 기본정리에 의해 아래의 합동방정식은 $p-1$개의 합동이 아닌 해들을 가진다.

$$ 0 \equiv x^{p-1} - 1 \equiv (x^{p-1 \over 2} +1) (x^{p-1 \over 2} -1) \pmod{p} $$

QR과 NR의 갯수: $2$ 보다 큰 소수 $p$ 에 대해 QR과 NR은 정확히 $\displaystyle {(p-1) \over 2}$ 개 존재한다

한편 소수 $p$ 에 대해 QR과 NR은 정확히 $\displaystyle {p-1 \over 2}$ 개씩 존재하는데, Case 1에서 본 것과 같이 $\displaystyle {p-1 \over 2}$ 개의 QR들은 $\displaystyle (x^{p-1 \over 2} -1) \equiv 0 \pmod{p}$ 의 해다. 즉 나머지 $\displaystyle {p-1 \over 2}$개의 NR들은 $(x^{p-1 \over 2} +1) \equiv 0 \pmod{p}$ 의 해여야만 한다. 따라서 다음이 성립한다. $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv -1 \pmod{p} $$

---

Case 1, 2를 종합하면 다음을 얻는다. $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p} $$

■