얼마전 베스트에 수학 사상 가장 우아한 증명이라는 게시글이 올라왔는데 어렵다는 댓글이 많아서 쉽게 정리를 해 보았어요.

http://todayhumor.com/?humordata_1999075

원게시글 클릭하기 귀찮으신 분들을 위해 이미지 퍼왔습니다요.

위의 설명대로 가장 큰 소수(prime number)가 존재한다고 가정하고, 그 가장 큰 소수를 p_n이라고 하자.

그리고 P를 다음과 같이 모든 소수의 곱에 1을 더한 수라고 하자.

P = p_1 * p_2 *.......*p_(n-1)*p_n + 1

P는 당연히 p_n보다 큰 수이고, 

P는 p_1, p_2, p_3, ......, p_(n-1), p_n 중 어느 소수와도 나누어 떨어지지 않는다.

이말인즉, P는 p_n 보다 큰 소수로 나누어 떨어지거나, 어느 소수로도 나누어 떨어지지 않는다.

즉, p_n보다 큰 소수는 존재할 수밖에 없다. <증명 끝>

그런데 위의 파란색 문장이 직관적으로 이해가 어려운데 아래와 같이 증명할 수 있습니다.

P가 p_1, p_2, p_3, ......, p_(n-1), p_n 중 하나의 소수와 나누어 떨어진다고 가정하고, 그 소수를 p_i라고 하자.

P = M*p_i

P는 p_i에 나누어 떨어지므로 M은 정수이다.

위의 식 양변을 p_i로 나누면,

P/p_i = M

{p_1*p_2*...*p_(i-1)*p_i*p_(i+1)*......*p_(n-1)*p_n + 1}/p_i = M

좌변을 풀어헤치면,

p_1*p_2*...*p_(i-1)*p_(i+1)*......*p_(n-1)*p_n + 1/p_i = M

좌변 첫번째 항은 정수이고, 두번째 항인 1/p_i는 정수가 아니다.

이는 M이 정수라는, 즉 P가 p_1, p_2, p_3, ......, p_(n-1), p_n 중 하나의 소수와 나누어 떨어진다는 가정에 모순.

따라서 P는 p_1, p_2, p_3, ......, p_(n-1), p_n 중 어느 소수와도 나누어 떨어지지 않는다. <증명 끝>