Mathematics : 귀류법으로 소수의 무한성 증명

귀류법

어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을, 즉 처음의 명제가 거짓임을 증명하는 방법

 

우선 결론부터 얘기하면, 소수는 무한하다.
유클리드는 BC 300년경 귀류법으로 소수의 무한성을 증명하였다.
귀류법으로 다음과 같이 증명할 수 있다.
우선 소수의 개수가 유한한 k개라고 가정해보자.

그리고 모든 소수를 다 곱하고 1을 더한 수를 n이라고 하자. n은 아래와 같이 표현할 수 있다.
n = P₁ * P₂ * P₃ * ... * Pₖ + 1 (P₁ = 첫 번째 소수, Pₖ = 마지막 소수)
이때 n은 제일 마지막 소수인 Pₖ보다 클 것이고, 위 명제가 참이라면 n은 합성수여야 한다.
소인수분해를 통해서 합성수는 소수들만의 곱으로 나타낼 수 있어야  되지만, n은 어떤 소수로 나누어도 나머지가 1이다.
이는 제일 마지막 소수인 Pₖ보다 더 큰 소수가 존재한다는 것이며, 가정에 대한 모순이다.
p → q 에서 참이라고 가정(p)했지만 결론(q)이 거짓이므로, 해당 명제는 거짓이다.
따라서 마지막 소수라는 것은 실제로 존재하지 않으며, '소수는 무한하다' 라는 것을 귀류법을 통해서 증명할 수 있었다.