차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

차이 보기로 연결

소수의무한성 [2011-05-30 18:25] (현재)
줄 1: 줄 1:
 +====== 소수의 무한성 ======
  
 +"[[소수]]는 무한히 많다"라는 [[정리]]. 좀 더 정확히는, 어떤 소수 $$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>수학}}

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