====== 소수의 무한성 ======

"[[소수]]는 무한히 많다"라는 [[정리]]. 좀 더 정확히는, 어떤 소수 $$p$$에 대해서도 그보다 큰 새로운 소수 $$p'$$가 존재한다는 정리이다:

<.center>$$\forall p \in \mathbb{P}.\, \exists p' \in \mathbb{P}.\, p' > p$$\\ ([[Metamath]]: [[metamath>infpn]])</>

===== 초등적 증명 =====

이 정리의 [[증명]]은 여러 방법으로 가능하지만, 가장 간단하고 [[유클리드]]가 저서 《[[원론]]》에서 사용했던 것과 유사한 방법은 다음과 같다:

> 소수의 갯수가 유한하다고 가정하자([[귀류법]]). 그러면 소수의 집합 $$\mathbb{P} = \{p_1, p_2, \cdots, p_n\}$$으로 표현할 수 있다. (편의상 $$p_1 < p_2 < \cdots < p_n$$으로 가정하자.)
> 이제 $$p' = \prod_{i=1}^n p_i + 1$$을 가정하면, 이 숫자는 $$\mathbb{P}$$에 있는 어느 숫자보다도 크므로 $$p' \not\in \mathbb{P}$$임이 자명하다. 그러나 모든 소수 모든 $$p_i$$에 대해 $$p' \equiv 1 \pmod{p_i}$$이므로 $$p'$$는 1과 자신을 제외한 [[소인수]]를 가지지 아니하고, 따라서 소수이다. 이는 $$p \not\in \mathbb{P}$$라는 가정에 모순되므로 최초의 가정은 틀렸다. 따라서 소수는 무한히 많다.

실제로 유클리드가 사용한 방법은 이와는 조금 다른데, 소수만을 담은 임의의 유한집합에 대해서 그 집합에 포함되지 않은 다른 소수가 존재함을 보인다. 이 경우 비슷한 방법으로 만들어진 값 $$p'$$는 소수이거나 [[합성수]]인데, 합성수일 경우 그 소인수는 비슷한 논리로 주어진 유한집합에 들어 있을 수가 없게 된다.

{{tag>수학}}