소수(prime number)의 개수는 무한할까?

 

 

여기서 말하는 소수는 0.1, 0.12 등의 소수가 아니라 1과 자기 자신만을 약수로 갖는 1보다 큰 자연수입니다. 2,3,5,7 등이 있습니다. 예를 들어 6은 1뿐만 아니라 2와 3을 약수로 갖기 때문에 소수가 아닙니다. 1보다 큰 수 중에서 소수가 아닌 수는 '합성수'라고 부릅니다. 1은 소수도 아니고 합성수도 아닙니다. 소수들을 합성해서 만들었다 뭐 그런 뜻인 것 같습니다. 합성수를 소수들의 곱으로 나타내는 것을 소인수분해라고 합니다. 소수는 마치 자연수의 '기본입자'같은 역할입니다. 소수는 더 이상 쪼개지지 않습니다. 

 

모든 합성수는 소인수분해가 가능할까요? 먼저 이 문장을 증명합시다.

 

소인수분해가 불가능한 작은 합성수를 n이라고 합시다. 소수가 아니므로 1과 자기자신 이외의 약수를 갖습니다. 이 약수를 m이라고 한다면 n은 m과 n/m 으로 나눠집니다. m과 n/m은 n보다 작은 수이므로 소인수분해가 가능하고, 따라서 n도 소인수분해가 가능하므로 가정에 모순입니다. 

 

따라서 모든 합성수는 소인수분해가 가능합니다

 

이제 소수가 개수가 무한한지 아닌지 알아봅시다. 

 

귀류법

소수가 유한개라고 가정합시다. n개라고 하겠습니다. $p_{1}$부터 $p_{n}$까지의 소수가 있습니다. 이때 아래와 같은 자연수가 존재합니다.

 

$p_{1}\times p_{2}\times \cdots\times p_{n}+1$

 

소수는 $p_{1}$부터 $p_{n}$까지라고 가정했으므로 위 자연수는 합성수로 분류되므로, 소인수분해가 가능해야 합니다. 우리가 정의한 어떤 소수로 나누어도 나누어 떨어지지 않고, 나머지가 1이기 때문입니다. 모순이 발생합니다. 따라서 소수가 유한개라는 가정은 틀린 것이 되고, 소수의 개수는 무한합니다. 

 

여기서 한가지 짚고 넘어갈 점은 $p_{1}\times p_{2}\times \cdots\times p_{n}+1$  가 실제로 소수인지 합성수인지는 중요하지 않다는 것입니다. 합성수일 수도 있고 소수일 수도 있습니다. 만약 2,3이 소수의 전부라고 가정했다면 2x3+1=7 이므로 소수가 될 것이고, 3,5가 소수의 전부라고 가정했다면 3x5+1=16이므로 합성수입니다. 이 증명의 핵심은 $p_{1}\times p_{2}\times \cdots\times p_{n}+1$ 가 실제로 소수냐 합성수냐가 아니라, 소수의 개수를 유한개로 정할 경우 소인수분해가 되지 않는 수가 등장한다는 것입니다. 

 

직접증명법

 

$p_{1}$부터 $p_{n}$까지의 소수가 있습니다. 소수가 유한개라고 가정한 것은 아닙니다. 어떤 소수 n개가 주어진 상황입니다. 이때 아래와 같은 자연수가 존재합니다.

 

$p_{1}\times p_{2}\times \cdots\times p_{n}+1$

 

(여기까지는 위 증명과 동일합니다.) 위 수는 소수이거나 합성수입니다. 위 수가 소수라면 주어진 n개와는 다른 새로운 소수입니다. 만약 위 수가 합성수라면 주어진 n개의 소수로는 소인수분해가 불가능 하므로, 새로운 소수의 존재가 확인됩니다. 따라서 어떤 n개의 소수가 주어지더라도 이보다 더 많은 소수가 항상 존재합니다.