소수의 무한성

소수의 무한성

소수는 무한히 많다.

 소수(素數, prime number)는 몇 개나 있을까? 소수를 순서대로 나열하면, 소수의 출현하는 데에는 규칙성이 없을 뿐만 아니라, 그 간격도 상당히 커기 때문에, 얼핏 봐서는 소수는 유한 개밖에 없지 않을까하는 생각이 든다. 소수가 유한 개만 존재하는지, 아니면 무수히 많은지 알아보자.

 소수가 무수히 많은지 여부는 대표적인 귀류법의 증명 내용 중 하나이다. 귀류법으로 다음과 같이 증명할 수 있다.

[1] 소수가 무수히 많음을 증명하시오.

(증명) 귀류법에 의해 증명하기 위해, 소수가 작은 순서대로 와 같이 유한 개 존재하며, 가장 큰 소수 이 존재한다고 가정하자. 그런데 이들 소수를 모두 곱해서 1을 더한, 는 로 나누어 모두 나누어 떨어지지 않기 때문에, 약수를 1과 자기 자신만 가지는 수이므로, 소수이다. 보다 큰 소수 가 존재하기 때문에 주어진 가정은 모순이다.

 주어진 바를 부정하였을 때, 모순이 생기므로 귀류법에 의해, 소수는 무수히 많음이 증명되었다. □

 이와 같이, 소수가 무수히 많음을 알 수 있다.

[참고] 위 증명에서, 굳이 귀류법으로 증명을 해야 하는지에 대한 의문을 제기할 수 있다. 즉, 소수를 유한 개 존재한다는 가정이 필요한지에 대한 의문을 제기할 수 있다. 이 가정은 반드시 필요한데, 이는 이 소수라는 것을 규명하기 위해서는 그것보다 작은 소수를 제한해야 하기 때문이다. 이렇게 제한하지 않을 경우, 보다 크고 보다 작은 어떤 소수가 존재할 수 있는 가능성을 배제할 수 없기 때문이다. 이와 같은 가능성을 배제하지 않을 경우, 나타나는 반례가

이다. 종종 이 반례 자체가 귀류법 증명 자체의 반례로 오해하는 경우가 있지만, 귀류법의 가정이 올바르게 되었다면, 위와 같은 예가 있어도 주어진 바는 증명이 된다.