소수의 개수는 무한

Postscriptum : 모바일로 접속해서 수식이 보이지 않는다면 PC버전으로 보자. 그러면 수식이 표현된다.

소수의 개수는 무한이다.

귀류법으로 접근하자. 소수의 개수가 유한이라고 하자. 크기순으로 $ x_i (i \in \mathbb{N}) $라고 하고 $ P = \prod_{i=1}^{n} x_i$라고 하면 $ x_{n} $이 최대의 소수이므로 $ P+1 $은 합성수 (Composite Number)이다. 따라서 $ P $는 어떤 하나의 소수 $ x $에 의해 나뉘어야 한다. 이 소수 $ x $는 $ x_i $ 중 하나이고 이들 중 어떤 수로 $ P+1 $을 나누어도 나머지는 1이 된다. 곧 인수로 $ x_i $를 가지지 않는다는 것이다. 결국 $ P+1 $은 합성수가 아니라는 모순에 이르게 되어 소수는 무한이라는 것을 증명할 수 있다.