정수론, 그 열한 번째 이야기 | 소수의 성질

 

소수의 정의는 앞선 글에서 다루었으므로, 이제 소수의 성질에 대해 알아보자.

우선 가장 중요한 성질을 고르자면, 아마 아래의 특징일 것이다.

 

Theorem 1.

소수는 무한히 많다.

 

Proof.

귀류법을 사용하여, 소수의 개수가 유한하다고 가정하고 모순을 이끌어내자.

 

소수가 유한하다면, 소수는 오름차순으로 $p_1 = 2,\;p_2 = 3,\;p_3 = 5,\;p_4 = 7\cdots$ 처럼 나타낼 수 있다.

그리고 마지막 소수, 즉 가장 큰 소수를 $p_n$ 이라고 하자.

 

이 때, 양수 $P = p_1 p_2 \cdots p_n + 1$ 을 생각해보자.

 

$P > 1$ 이므로 산술의 기본정리에 의해 $P$ 는 어떤 소수 $p$ 에 의해 나누어진다.

그러나 $p$ 는 소수이므로, $p_1,\;p_2,\;\cdots\;p_n$ 중 하나이다.

 

따라서, $p \mid p_1 p_2 \cdots p_n$ 이고, $p \mid P = p_1 p_2 \cdots p_n + 1$ 이다.

 

이는 곧 $p \mid \left ( P - p_1 p_2 \cdots p_n \right ) = 1$ 을 의미하는데, $p$ 는 소수이므로 $p \nmid 1$ 이다.

 

따라서 이는 모순이고, 처음의 가정이 거짓이다.

따라서 소수는 무한히 많다.

$\blacksquare$

 

또, 위의 증명을 모방하여 $n$ 번째 소수인 $p_n$ 의 크기에 대한 성질을 알 수 있는데, 이는 다음과 같다.

 

Theorem 2.

$p_n$ 을 $n$ 번째 소수라고 하면, $p_n \leq p_1 p_2 \cdots p_{n-1} + 1$ 이 성립한다.      단, $n$ 은 $2$ 이상의 자연수이다.

 

Proof.

위의 부등식을 증명하기 위해, 우리는 양수 $P = p_1 p_2 \cdots p_{n-1} + 1$ 을 생각하자.

이 때, 산술의 기본정리에 의해 $P$ 는 어떤 소수 $p$ 로 나누어진다.

 

그런데 $p \leq p_{n-1}$ 이면 $p \mid p_1 p_2 \cdots p_{n-1}$ 이고 $p\mid P = p_1 p_2 \cdots p_{n-1}+1$ 이므로 $p \mid 1$ 이 되어 모순.

 

즉, $p > p_{n-1}$ 이고 이는 $p \geq p_n$ 을 의미한다. 그런데 $p \mid P$ 가 성립하므로$$p_n \leq p = |p| \leq |P| = P$$ 이다. 따라서, $p_n \leq P = p_1 p_2 \cdots p_{n-1} + 1$ 이 성립한다.

$\blacksquare$

 

그런데 위의 부등식은 $p_n$ 의 최대 크기를 알기 위해서 $p_1,\;p_2\;\cdots\;p_{n-1}$ 의 크기를 알 필요가 있다.

그렇기 때문에 우리는 앞에 나오는 소수와 무관하게 $p_n$ 의 최대 크기를 알려주는 명제를 증명할 것이다.

 

Theorem 3.

$p_n$ 이 $n$ 번째 소수이면, $p_n \leq 2^{2^{n-1}}$

 

Proof.

증명을 위해 $n$ 에 대해 수학적 귀납법을 사용하자.

만약 $n = 1$ 이면, 위 부등식은 $p_1 = 2 \leq 2^{2^0} = 2$ 이므로 참이다.

 

이제 어떤 자연수 $k$ 에 대해, $n = 1,2,\cdots, k$ 일 때 위의 부등식이 참이라고 가정하자.

 

이 때, $p_{k+1} \leq p_1 p_2 \cdots p_k + 1$ 이 성립하므로 이 부등식은 $$p_{k+1} \leq p_1 p_2 \cdots p_k + 1 \leq 2\cdot 2^2 \cdot 2^4 \cdots 2^{2^{k - 1}} + 1 = 2^{1 + 2 + 2^2 + \cdots 2^{k-1}} + 1$$ 로 바뀐다. 그런데 임의의 자연수 $n$ 에 대해 $1\leq 2^{2^n-1}$ 이고, $1+2+2^2 + \cdots 2^{n-1} = 2^n-1$ 이므로 $$p_{k+1}\leq 2^{2^k-1} + 2^{2^k-1} = 2^{2^k}$$ 가 되어, 위의 부등식이 성립한다.

 

따라서 수학적 귀납법에 의해, 모든 자연수 $n$ 에 대해 $p_n \leq 2^{2^{n-1}}$ 이 성립한다.

$\blacksquare$

 

우리는 위의 정리로부터 자연수 $n$ 에 대해 $2^{2^n}$ 보다 작은 소수는 적어도 $n + 1$ 개임을 알 수 있다.

$p_1,\;p_2,\;\cdots,\;p_{n+1}$ 이 모두 $2^{2^n}$ 보다 작기 때문이다.

 

 

그러나 위에서 구한 $n$ 번째 소수의 최댓값은 그리 좋은 결과를 얻은 것은 아니다.

실제로 $10$ 번째 소수는 $29$ 인데 반해, $2^{2^{10-1}}$ 의 값은 $1.3 \times 10^{154}$ 이상의 매우 큰 수이기 때문이다.

 

그러나 우리는 베르트랑의 공준(버트란드의 공준이라고도 부른다)을 통해 위에서 구한 값보다 좋은 최댓값을

알 수 있다. 그러나 이는 어려운 증명과정으로 인해 결과만 소개하고, 증명은 차후에 다루도록 하겠다.

 

베르트랑의 공준은 아래의 명제이다.

 

$2$ 이상의 정수 $n$ 에 대해, $n < p < 2n$ 을 만족하는 소수 $p$ 가 항상 존재한다.