본문 바로가기

나는 공돌이다

리만가설 이야기를 읽다가

관련링크: 리만가설 이야기 - 에라토스테네스의 체


에라토스테네스의 체를 n까지 하고 나면 가장 작은 합성수는 n^2이 된다.는 부분이 있다.

증명해보았다. 어렵지 않았음.


귀류법을 쓴다. n^2보다 작은 합성수가 있다고 치자. 그 수를 m이라고 하면 m은 다음과 같이 표현할 수 있다.

m = a x b

a,b 둘 중 적어도 하나는 n보다 작을 것이다. 그렇지 않다면 m<n^2을 만족하지 못한다.

a<n이라고 하자. a는 소수일 것이다. 체를 n까지 쳤으니까. 

그럼 여기서 모순이 발생한다. 

에라토스테네스의 체를 n까지 쳤으니까 n보다 작은 소수인 a의 배수는 남아있지 않아야 하니까.

증명 끝.

'나는 공돌이다' 카테고리의 다른 글

헤더파일 중복 막기  (2) 2016.02.26
아이맥의 절전모드와 대기모드  (0) 2016.02.25
스크립트 언어 vs. 컴파일 언어  (0) 2016.02.21
C++ 교재  (0) 2015.08.22
필요조건, 충분조건, 필요충분조건  (0) 2015.08.19