특정한 꼴의 소수

$4n - 1$ 꼴의 소수는 무한히 많다.

 

Proof

만약 $4n-1$ 꼴 소수가 유한하다면, 그 중 최대의 소수를 $p$ 라 놓을 수 있습니다. 그렇다면 $$N = 2^2 \cdot 3 \cdot 5 \cdot \cdots \cdot p - 1$$ 이라 두었을 때, $N > 1$ 이며 $N$ 은 $4n-1$ 꼴의 수입니다. 그런데 $N$ 은 어떤 $4n-1$ 꼴 소수로도 나누어지지 않으므로 $N$ 의 소인수로는 $4n+1$ 꼴 소수만 가능합니다. 하지만 $4n+1$ 꼴의 두 수를 곱한 결과도 여전히 $4n+1$ 꼴이므로 이는 모순입니다. 따라서 $4n-1$ 꼴 소수는 무한합니다.

 

$4n+1$ 꼴의 소수는 무한히 많다.

 

Proof

임의의 자연수 $N > 1$ 에 대해, $p > N$ 이고 $p \equiv 1 \mod 4$ 인 소수 $p$ 가 존재함을 보이겠습니다. $$m = (N!)^2 +1$$ 이라 놓으면, $m > 1$ 이고 $m$ 은 홀수입니다. 이제 $m$ 의 소인수 중 최소인 것을 $p$ 라 두면, $2, 3, \cdots, N$ 은 $m$ 을 나누지 못하므로 $p > N$ 입니다. 또, $$(N!)^2 \equiv -1 \mod p$$ 이므로 $$(N!)^{p-1} \equiv (-1)^{\frac{p-1}{2}} \mod p$$ 입니다. 이는 오일러 페르마 정리에 의해 $$(-1)^{\frac{p-1}{2}}\equiv 1 \mod p$$ 가 되고, $p > 2$ 이라면 반드시 $$(-1)^{\frac{p-1}{2}} = 1$$ 입니다. 이는 $\frac{p-1}{2}\equiv 0 \mod 2$ 라는 뜻이고, 따라서 $p \equiv 1 \mod 4$ 입니다.

 

임의의 자연수 $N > 1$ 에 대해 $p > N$ 인 $4n+1$ 꼴 소수가 존재하므로, $4n+1$ 꼴 소수는 무한합니다.