프로트의 정리 는 다음과 같습니다.
프로트의 정리이 정리만 해도 꽤나 강력한데, 여기서 더 발전 시킬 수 있습니다.
프로트 수 $N$에 대하여, $$ a^{\frac{N - 1}{2}} \equiv -1 \pmod{N} $$ 인 자연수 $a$가 존재한다면, $N$은 소수 이다.
$d$가 3의 배수가 아닌 $3$보다 큰 프로트 수 $N = d \times 2^{s} + 1$에 대하여, $$ 3^{\frac{N - 1}{2}} \equiv -1 \pmod{N} $$ 이면 $N$은 소수이고, 그 외의 경우는 합성수이다.$d$가 3의 배수인 경우에는 다음과 같이 확장 할 수 있습니다.
$d$가 5의 배수가 아니고 $N \not\equiv 4 \pmod{5}$인 프로트 수 $N = d \times 2^{s} + 1$에 대하여, $$ 5^{\frac{N - 1}{2}} \equiv -1 \pmod{N} $$ 이면 $N$은 소수이고, 그 외의 경우는 합성수이다.
$3$보다 큰 $N$이 소수이면 르장드르 기호 $\left(\frac{3}{N}\right)$에 대해 오일러의 규준 에 의해 $\left(\frac{3}{N}\right) \equiv 3^{\frac{N - 1}{2}} \pmod{N}$ 이다.
$N = d \times 2^{s} + 1$에서, $(-1)^{\frac{N - 1}{2}} = (-1)^{\frac{d \times 2^{s}}{2}}$ 이다.
이차 상호 법칙 에 의해 $\left( \frac{3}{N} \right) \left( \frac{N}{3} \right) = (-1)^{\frac{(3 - 1) (N - 1)}{4}}$ 인데, $(-1)^{\frac{N - 1}{2}}$ 값을 계산하면 된다.
식 계산
$d$가 홀수이고, 프로트 수의 정의에 의해서 $d < 2^{s}$이므로, $s = 1$인 프로트 수는 오직 $1 \times 2^{1} + 1 = 3$이다. 애초에 이차 상호법칙은 서로 다른 두 소수에 대해서만 성립하므로 이 부분은 무시할 수 있다.
$3$이 아닌 프로트 수는 모두 $s \geq 2$이므로, $(-1)^{\frac{d \times 2^{s}}{2}}$에서 $(-1)^{d \times 2^{s - 1}}$이고, $1 = (-1)^{2}$에서 $(-1)^{d \times 2^{s - 1}} = 1^{d \times 2^{s - 2}}$이다.
$s \geq 2$에서 $d \times 2^{s - 2}$는 정수이므로, $(-1)^{\frac{N - 1}{2}}$ 값은 $1$이 된다.
이때, $d$가 $3$의 배수가 아니라는 전제조건에 유의하면서, $d \times 2^{s}$가 $3$의 배수이려면 $2^{s}$가 $3$의 배수여야하는데 당연히 불가능하다.
따라서 $d \times 2^{s}$는 $3$의 배수가 될 수 없고, $d \times 2^{s} \not\equiv 0 \pmod{3}$에서 $N = d \times 2^{s} + 1 \not\equiv 1 \pmod{3}$이다.
또, $N$은 $3$보다 큰 소수라고 했으니 $3$의 배수일 수 없으므로, $N = d \times 2^{s} + 1 \not\equiv 0 \pmod{3}$이고, 따라서 $N \pmod{3}$ 로 가능한 것은 $2 \pmod{3}$ 뿐이다.
따라서, $\left( \frac{N}{3} \right) = \left( \frac{2}{3} \right)$이고, $\left( \frac{2}{3} \right) = -1$이다.
오일러의 규준에 의해 $-1 = \left( \frac{2}{3} \right) = \left(\frac{3}{N}\right) \equiv 3^{\frac{N - 1}{2}} \pmod{N}$ 이므로, "$d$가 $3$의 배수가 아닌 $3$보다 큰 프로트 수 $N$이 소수이면 -> $3^{\frac{N - 1}{2}} \equiv -1 \pmod{N}$" 이다.
"$d$가 $3$의 배수가 아닌 $3$보다 큰 프로트 수 $N$이 합성수인데 -> $3^{\frac{N - 1}{2}} \equiv -1 \pmod{N}$"이다 라는 문장은 불가능하다. 프로트의 정리 에 의해 $a^{\frac{N - 1}{2}} \equiv -1 \pmod{N}$ 인 $a$가 존재하면 무조건 소수이기 때문이다.