소수의 무한성

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

\forall p \in \mathbb{P}.\, \exists p' \in \mathbb{P}.\, p' > p
(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'는 소수이거나 합성수인데, 합성수일 경우 그 소인수는 비슷한 논리로 주어진 유한집합에 들어 있을 수가 없게 된다.


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기