소수의 개수가 무한개인 이유 증명

소수란? 1보다 크고, 1과 자기 자신을 제외한 다른 수로는 나누어지지 않는 수를 말한다. 그래서 소수를 수의 원자라고도 한다.(약수가 1과 자기 자신뿐이기 때문이다.) 이러한 소수가 무한개인 이유를 2가지 방법으로 증명해보자.

 

1. 첫번째 증명방법

소수의 개수가 유한하다고 가정해보면, 가장 큰 소수 $P$가 존재한다. (2, 3, 5, 7, 11,..., P(가장 큰 소수)) 이때, 모든 소수들을 곱한 값에 1을 더한 값을 $N$이라 하자.

 

$N =(2\times3\times5\times7\times11\times\cdots\times P)+1$ 이다. 이때, $N$은 가장 큰 소수 $P$보다 더 큰 숫자이므로 소수가 아니다. 소수가 아니라면, 어떤 소수로 반드시 나누어져야만 한다. $N$을 소수의 크기순서대로 나누어보자.

 

먼저 $N$을 2로 나누어보자.

$N =(2\times3\times5\times7\times11\times\cdots\times P)+1$이고, 2가 곱해져 있으므로 괄호 안의 부분은 짝수이고, $N$은 홀수임을 알 수 있다. 따라서 N은 2로 나누어 떨어지지 않는다.

 

$N$을 3으로 나누어보자.

$N =(2\times3\times5\times7\times11\times\cdots\times P)+1$ 이고,괄호 부분은 3의 배수이다. 괄호 부분보다 1이 더 큰 $N$은 3으로 나누어 떨어지지 않는다.

 

$N$을 5로 나누어보자.

$N =(2\times3\times5\times7\times11\times\cdots\times P)+1$ 이고 괄호 부분은 5의 배수이다. 괄호부분보다 1이 더 큰 $N$은 5로 나누어 떨어지지 않는다.

 

이렇게, 모든 소수로 N을 나누는 과정을 반복하면, $N$은 어떤 소수로도 나누어지지 않는다. 즉, $N$이 소수이다. 이는 P가 가장 큰 소수라는 것에 모순이다. 이것은 소수가 유한개라는 가정에 모순된다. 따라서 소수의 개수는 무한개이다.

 

2. 두번째 증명방법

소수의 개수가 유한하다고 가정해보면, 가장 큰 소수 $P$가 존재한다.

모든 소수들을 곱한 값을 $N$이라고 하자.

$N=2\times3\times5\times7\times\cdots\times P$이다.

 

1~$N$까지의 자연수에 대해서 2의 배수는 $\frac{N}{2}$개이다. 2의 배수를 모두 지우면, 남은 자연수의 개수는 $N\times\frac{1}{2}$이다.

 

이 남은 자연수들 중에서 3의 배수의 개수는 $\frac{N}{3}$개이다. 3의 배수를 모두 지우면, 남은 자연수의 개수는 $N\times\frac{1}{2} \times\frac{2}{3}$이다.

 

또다시 남은 자연수에 대해서 5의 배수의 개수는 $\frac{N}{5}$개이다. 5의 배수를 모두 지우면, 남은 자연수의 개수는 $N\times\frac{1}{2} \times \frac{2}{3} \times \frac{3}{4}$이다.

 

모든 소수의 배수를 지우는 과정을 반복한다면, 남은 자연수의 개수는 $N\times\frac{1}{2}\times\frac{2}{3}\times\frac{3}{4}\times\cdots\times\frac{P-1}{P}$ 개이고, 이 값은 1이어야만 한다.(왜냐하면, 모든 소수의 배수를 다 지웠기 때문)

 

하지만, 이 값을 계산해보면, $N\times\frac{1}{2}\times\frac{2}{3}\times\frac{3}{4}\times\cdots\times\frac{P-1}{P}=1\times2\times4\times6 \times\cdots \times(P-1)>1$이다. 즉, 이 값은 1보다 크다. 따라서 남아있는 개수가 1보다 크므로 모순이다. 따라서 소수의 개수는 무한개이다.

소수 개수 무한