소수는 무한히 존재한다(infinity of prime number)

 

소수(prime number)가 무한히 많음을 증명하도록 하겠습니다.

 

 

귀류법적으로 접근하기 위해 먼저 '소수가 유한하다'는 것을 가정하도록 합시다.

 

그리고 소수를 작은 순서부터 나열한 수열을$P_n$이라고 합시다.

 

마지막 소수를 $P_k$라고 가정합시다. 소수는 유한하므로 모든 소수를 나열하여 곱할 수 있습니다.

 

모든 소수의 곱은 $P_1P_2P_3P_4 \cdots P_iP_{i+1} \cdots P_k$가 됩니다.

 

이 수를 이용하여 이러한 식을 만들 수 있습니다.

$P = P_1P_2P_3P_4 \cdots P_iP_{i+1} \cdots P_k+1$

 

$P$는 '모든 소수의 나열을 곱한 것'에 1을 더한 것이죠. 자세히 보시면 $P$는 $P_1$으로도 $P_2$로도 소수의 마지막 나열인 $P_k$로도 나뉘지 않는다는 것을 알 수 있습니다. 즉, 다시 말해서 $P$는 임의의 소수 $P_i$에 대해서 나눠지지 않습니다.

 

이는 $P$가 소수라는 걸 의미하고, $P$가 소수라는 건 우리가 처음에 가정했던 '소수는 유한하다'는 것에 모순입니다.

 

$P$에 의해서 소수는 무한히 발견되므로, 따라서 가정인 '소수가 유한하다'는 것은 잘못되었고 귀류법에 의해서 소수는 무한히 존재합니다.

 

 

또한 자연수집합 $\mathbb{N}$과 소수의 집합 $\mathbb{P}$는 일대일 대응됨을 알 수 있습니다.

 

소수의 수열 $P_n$은 무한히 나열될 수 있고, 그 나열되는 수마다 자연수 $n$을 각각에 대응할 수 있습니다.

 

즉, $n$과 $P_n$이 무한히 대응됩니다.

 

이는 $\mathbb{P}$가 무한집합이면서 자연수의 부분집합이기 때문에 non-denumerable할 수 없고, 따라서 denumerable이기 때문에 성립하는 명제이기도 합니다.