프로트의 정리
프로트의 정리 (Proth's Theorem) 는 다음과 같습니다.
프로트 수 $N$에 대하여,
$$
a^{\frac{N - 1}{2}} \equiv -1 \pmod{N}
$$
인 자연수 $a$가 존재한다면, $N$은 소수 이다.
페르마의 소정리 와 상당히 비슷한 듯 싶지만, 페르마의 소정리와 약간은 다르게 위 식을 만족하는 $a$가 존재하기만 해도 소수라고 할 수 있을 정도로 상당히 강력한 정리입니다.
프로트의 정리 증명
전제 조건 1. $N$은 프로트 수이다. (즉, $d < 2^{s}$, $N = d \times 2^{s} + 1$)
전제 조건 2. 어떤 자연수 $a$에 대하여 $a^{\frac{N - 1}{2}} \equiv -1 \pmod{N}$이라는 결과가 나왔다.
보조정리 1. 페르마의 소정리
모든 소수 $p$에 대하여 $a$와 $p$가 서로소이면 $a^{p - 1} \equiv 1 \pmod{p}$이다.
보조정리 2. 모듈러 연산 (나머지 연산) 관련
$a \equiv b \pmod{c d}$이면, $a \equiv b \pmod{c}$이다.
보조정리 2 증명
$x \equiv y \pmod{z}$이면 어떤 자연수 $k$에 대해 $x - y = zk$이다.
$a \equiv b \pmod{c d}$ 에서 어떤 자연수 $k$에 대해 $a - b = cdk$이고, $dk = K$로 치환하면 $a - b = cK$에서 $a \equiv b \pmod{c}$ 라 할 수 있다.
보조정리 3. 위수 성질 관련
$b^{2^{n - 1}} \equiv -1 \pmod{q}$, $b^{2^{n}} \equiv 1 \pmod{q}$이면 $\operatorname{ord}_{q} b = 2^{n}$이다.
보조정리 3 증명
$N$이 합성수라면 $N$의 소인수이면서 $\sqrt{N}$ 이하인 소인수 $q$가 존재한다.
$b = a^{d}$라 하면, $a^{\frac{N - 1}{2}} \equiv -1 \pmod{N}$은 $b^{2^{s - 1}} \equiv -1 \pmod{N}$가 된다.
$N$ = $q \frac{N}{q}$이고, $\frac{N}{q}$는 정수이므로($q$가 $N$의 약수), $b^{2^{s - 1}} \equiv -1 \pmod{N}$ 에서 $b^{2^{s - 1}} \equiv -1 \pmod{q}$가 성립한다.
양 변을 제곱하면 $b^{2^{s}} \equiv 1 \pmod{N}$이므로, $b^{2^{s - 1}} \equiv -1 \pmod{N}$, $b^{2^{s}} \equiv 1 \pmod{N}$에서 $\operatorname{ord}_{q} b = 2^{s}$ 이다.
이때, $b = a^{d}$는 $q$와 서로소이므로, 페르마의 소정리에 의해 $b^{q - 1} \equiv 1 \pmod{q}$이다.
$\operatorname{ord}_{q} b = 2^{s}$인데, $b^{q - 1} \equiv 1 \pmod{q}$이므로 위수의 성질에 의해 $2^{s}$는 $q - 1$의 약수이다.
$2^{s}$는 $q - 1$의 약수이므로 $2^{s} \leq q - 1$이고, $q \leq \sqrt{N}$에서 $q - 1 < \sqrt{N}$이므로, $2^{s} \leq q - 1 < \sqrt{N}$이다.
이때, $2^{s} < \sqrt{N}$ 이므로 양 변을 제곱하면 ${\left( 2^{s} \right)}^{2} < N$이다.
그런데, $d < 2^{s}$, $N = d \times 2^{s} + 1$ 에서 $N - 1 = d \times 2^{s} < {\left( 2^{s} \right)}^{2} < N$에서, $S = {\left( 2^{s} \right)}^{2}$라 하면 $N - 1 < S < N$인 정수 $S$가 있어야 하는데, 그러한 정수는 없으므로 모순이다.
따라서, $N$은 소수이다.