귀류법으로 소수가 무한함을 증명하다

귀류법이 무엇인지 자세히 알고 싶으면 귀류법으로 2의 제곱근이 유리수가 아님을 증명하다를 읽어 보기 바랍니다.

[증명]소수는 유한하지 않다.

이 내용은 BC 300년경에 활약한 그리스의 수학자 유클리드가 기록한 증명입니다.

'소수는 유한하다'고 가정합니다.


는 소수의 집합입니다. 위의 소수집합에서 자연수 를 생각할 수 있습니다. 은 보다 크므로 소수집합에 속하지 않는 합성수입니다. 합성수란 소수 곱으로 이루어진 자연수입니다.

합성수 을 어떤 소수로 나누면 나누어집니다. 어떤 소수 로 을 나누면 아래와 같습니다.


부분은 가 어떤 소수가 되던 반드시 나누어집니다. 하지만 는 어떤 소수로도 나누어지지 않습니다. 따라서 은 나누어지지 않습니다.

합성수 은 소수집합 의 어떤 수로도 나누어지지 않으므로 이 합성수가 아니거나 집합 외에 다른 소수가 있습니다. 그러므로 '소수는 유한하다'는 거짓입니다.

유한하지 않은 모든 것은 무한하므로 소수는 무한합니다.


예를 들어
이라 하면 가 되어 새로운 소수 와 가 있어야 합니다.