| 소수(Prime Number)의 무한성 증명
유클리드의
증명
시작부터 오직 유한 개의 소수만이 존재한다고 가정하고, 이
가정으로부터 모순을 끌어 내면 된다.
먼저 소수가 유한하다고
가정하자. 소수가 유한하면 우리는 소수를 2, 3, 5, ...., 151, ...P처럼
나열할 수 있다. 여기서 P는 가장 큰 소수이다. 이렇게 나열된 소수를
모두 곱하면, 우리는 새로운 수 N=2 X 3 X 5 x ... X 151 X ... X P를
얻게 된다. 이제 새로 만든 수 N 보다 1이 큰 N+1을 자세히 살펴보자.
(N+1)이 2로 나누어 떨어지는지 살펴보자. 나누어지면 나머지는 0이
되고, 나누어 떨어지지 않으면 나머지는 1이 될 것이다. 그런데 2는
N의 인수이므로 (N=2 X 3 X ... X P), N은 2로 나누어진다. 이 사실은
동시에 (N=1)이 2로 나누어지지 않음을 의미한다. 즉 수 (N+1)을 2로
나눈 나머지는 1이다. 나아가 3 역시 N 의 인수이므로 N 은 3으로 나누어진다.
따라서 (N+1)은 N보다 1이 큰 수이므로 (N+1)을 3으로 나눈 나머지 또한
1이 된다. 5, 7, 그리고 P까지 모든 소수들의 경우에도 마찬가지다.
즉 N은 어떤 소수로도 나누어지는 반면에, (N+1)은 어떤 소수로도 나누어
떨어지지 않고 항상 나머지 1이 남는다.
이것은 무엇을 의미하는가?
(N=1)은 모든 소수 2, 3, 5, ..., P에 대해 나누어지지 않으므로 수
(N+1)에 관해 우리는 다음 2가지 경우를 생각할 수 있다. 수 (N+1)은
P보다 더 큰 어쩐 소수에 의해 나누어진다. 우리는 이미 P가 가장 큰
소수라고 가정했으므로 첫번째 경우는 명백히 거짓이다. 따라서 두번째
경우가 성립해야 한다. 두번째 경우가 성립하려면 가장 큰 소수 P보다
더 큰 어떤 소수가 존재해야 한다. 이것 역시 소수가 유한하다는 원래
가정에 위배된다. 그러므로 가장 큰 소수란 없으며, 따라서, 무한히
많은 소수가 존재한다.
(1998년 1월 1일 하창호)
|