리만가설 이야기를 읽다가

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

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

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

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

m = a x b

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

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

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

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

증명 끝.