오일러의 규준

오일러의 규준(Euler's criterion)은 어떤 소수 및 그와 서로소인 자연수가 주어질 때 르장드르 기호의 값을 판별하는 공식이다.

공식

[math]\displaystyle{ p }[/math]가 홀수인 소수이고 이와 서로소인 [math]\displaystyle{ a }[/math]가 있다. 아래 공식은 이차잉여 여부를 결정한다.

[math]\displaystyle{ a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod p & (\exists x\in \mathbb{Z})[x^2 = a]\\ -1 \pmod p & (\forall x\in\mathbb{Z})[x^2\neq a] \end{cases} }[/math]

르장드르 기호로 표현하면 [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod p }[/math]이다.

증명

페르마의 소정리에 의해 합동식 [math]\displaystyle{ a^{p-1} \equiv 1 \pmod p }[/math]이 성립하며, 제곱근을 취하면 [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p }[/math]이다.

[math]\displaystyle{ a }[/math]가 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여이면 [math]\displaystyle{ x^2 \equiv a \pmod p }[/math]인 [math]\displaystyle{ x }[/math]가 존재하므로, [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod p }[/math]임을 알 수 있다. 두 번째 합동 기호는 페르마의 소정리를 적용한 것이다.

한편 라그랑주의 정리에 따르면 [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv 1 \pmod p }[/math]는 [math]\displaystyle{ a }[/math]가 미지수인 [math]\displaystyle{ \frac{p-1}{2} }[/math]차 합동식이므로, 해당 합동식의 해는 [math]\displaystyle{ \frac{p-1}{2} }[/math]개 이하이다. 그런데 법 [math]\displaystyle{ p }[/math]에 대한 서로 다른 이차잉여는 [math]\displaystyle{ \frac{p-1}{2} }[/math]개이며 각 이차잉여는 해당 합동식을 만족한다. 그러므로 이차잉여 외 값은 이 합동식의 해로써 추가로 들어갈 수 없다.

따라서 [math]\displaystyle{ a }[/math]가 법 [math]\displaystyle{ p }[/math]에 대한 이차비잉여이면, [math]\displaystyle{ a^{\frac{p-1}{2}} \not \equiv 1 \pmod p }[/math]이고, 첫 문단의 조건에 의해 [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv -1 \pmod p }[/math]이다.

따름정리

[math]\displaystyle{ \gcd(a, p)=\gcd(b, p)=1 }[/math]일 때, [math]\displaystyle{ \left(\frac{ab}{p}\right) \equiv (ab)^{\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}}b^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \pmod p }[/math]

르장드르 기호 값은 ±1이므로 [math]\displaystyle{ \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) }[/math]와 같이 정리할 수 있다.

이차잉여 여부 판별

법 [math]\displaystyle{ p }[/math]에 대한 모든 이차잉여를 구하고 싶다면 [math]\displaystyle{ r^2 \mod p\ (1 \leq r \leq \frac{p-1}{2}) }[/math]를 차례대로 셈하면 된다. 그런데 [math]\displaystyle{ p }[/math]가 큰 소수이고 임의의 특정한 값이 이차잉여인지 여부를 알고 싶다면, 이차 상호 법칙이나 오일러의 규준을 이용하는 것이 빠르다.