소수의 무한성에 대한 네 가지 증명

자연수 집합이 무한히 많은 소수를 포함한다는 사실은 고전적이고 일반적인 결과인 만큼 오래전부터 수많은 방법으로 증명되어 왔다. 그중 가장 유명한 것은 유클리드의 증명일 것이다.

소수가 유한하다고 가정하고 그들을 크기 순서대로 \( p_1,\,p_2, \cdots , p_k \) 라 하자. 그리고 다음과 같은 자연수를 새로 정의한다.

\[ N = p_1 p_2 p_3 \cdots p_k +1\]

\( p_1 =2 > 1 \)이므로 \( N > p_k\)이고 \( p_k\)는 가장 큰 소수이므로 \( N \)은 소수가 아니다. 그러나 모든 \( i = 1,2,3, \cdots k\)에 대해 \( N\)을 \( p_i \)로 나눈 나머지가 1이므로 \(N\)은 어떠한 소수로도 나누어 떨어지지 않는다. 따라서 \(N\)은 소수이다. 이는 \( N\)이 소수가 아니라는 사실에 모순이며, 따라서 소수는 무한하다.

그러나 여러 명제가 그러하듯이 소수의 무한성을 증명하는 방법은 하나가 아니다. 이 글에서는 비교적 덜 유명한 증명들을 소개한다. 그들은 해석학, 위상수학 등 정수론과는 전혀 상관 없는 것으로 보이는 이론에 기반을 두고 있는 경우도 있다.

에르되시의 증명

소수가 유한하다고 가정하고 그들을 \( p_1,\,p_2, \cdots , p_k \) 라 하자. 우리는 \(k\)를 이용해 정수 집합 전체를 덮을 것이다.

pf)

위 조건을 만족하는 표현을 \( n=r_1 {s_1}^2 = r_2 {s_2}^2 \)라 두고 \( s_1 \neq s_2\)라 하자. 그러면 \(s_1\)과 \(s_2\)의 (지수 0을 포함한) 소인수분해에서 하나의 소인수의 차수가 다르다. 일반성을 잃지 않고 소수 \( q\)와 \(a \in \mathbb{N}_0\)에 대해 \(q^a \mid s_1,\,s_2\)이지만 \( q^{a+1} \nmid s_2\)이고 \( q^{a+1} \nmid s_1\)이라고 하자. 그러면 등식

\[r_1 {s_1}^2 = r_2 {s_2}^2 \]

에서 \( q^{2a+2}\)은 양변을 나누어야 한다. 그러나 좌변의 \( {s_1}^2\)엔 \(q\)가 \(2a\)개 뿐이기 때문에 \(q^2\)이 \(r\)을 나누어야 한다. 이는 처음 가정에 모순이므로 \( s_1=s_2\)이고 따라서 \(r_1=r_2\)이다.

proved

이제 어떤 자연수 \(N\)에 대해 \(N\) 이하의 모든 자연수를 이와 같은 방법으로 표현하는 경우의 수의 총합을 생각해보자. 각각의 \(n \leq N\)은 유일하게 표현되므로 그 경우의 수의 총합은 \(N\)이다. 그리고 \(N\) 이하의 자연수 중 그러한 꼴로 쓰여질 수 있는 것의 널널한 상계를 구해보자.

우선 \(r \geq 1\)이므로 \(s \leq \sqrt{N}\)이다. 그리고 어떠한 소수의 제곱으로도 나누어지지 않는 자연수는 다음과 같은 꼴을 띠어야 한다는 것을 관찰한다.

\[ r = p_{1}^{\epsilon_1}p_{2}^{\epsilon_2}\cdots p_{k}^{\epsilon_k} \qquad (\epsilon_i =0,1)\]

그러면 가능한 \(r\)의 총 개수는 \(2^k\)개이다. 따라서 \(N\)이하의 모든 자연수 중 이와 같은 꼴의 자연수의 개수의 상한은 \(\sqrt{N}2^k\)이다.

\[ N \leq \sqrt{N}2^k\]

\[ N \leq 4^k\]

여기서 \(k\)는 증명의 시작에서 가정한 소수의 개수, 즉 고정된 하나의 자연수이다. 간단하게 \( N = 4^k +1\)을 위 논증에 대입하면 즉시 모순이 발생한다. 따라서 소수는 무한하다.

Fürstenberg의 증명

Fürstenberg는 정수 집합에 적당한 위상을 부여해 소수가 무한하다는 사실을 증명했다.

그의 증명을 이해하기 위해서는 위상과 기저에 대한 기본적인 이해가 필요하다.

얼핏 보면 상관 없어보이는 두 정의는 아래 정리를 통해 강하게 연결된다.

정리의 증명이 아주 어려운 것은 아닐 뿐더러 소수의 무한성 증명에 있어 필수적이지 않기 때문에 생략한다. 본격적인 증명에 돌입하기 전에 아래 정의로 용어를 정리하고 넘어간다.

우선 소수가 유한하다고 가정하자.

다음과 같이 정의된 \( \mathcal{B}\)는 \(\mathbb{Z}\) 상에서의 기저이다. 증명은 간단하니 생략한다.

\( S(1,b)\)를 생각하면 기저의 첫번째 조건을, \(a_1\)과 \(a_2\)의 공배수를 생각하면 기저의 두번째 조건을 만족시킴을 확인할 수 있다. 그리고 \( \mathcal{B}\)로 생성된 위상 \( \mathcal{T}\)의 특별한 성질을 살펴보자.

증명의 핵심은 집합

\[ \bigcup_{p \,:\, prime} S(p,0)\]

를 다루는 것이다. 우선 이 집합은 소수의 유한성 가정과 위 성질 2에 의해 닫힌 집합의 유한 합집합 꼴이다. 그리고 닫힌 집합의 유한 합집합은 그 여집합이 열린 집합의 유한 교집합(즉, 열린 집합)으로 나타나야 한다. 이때 위 집합의 여집합을 생각해보면, 절댓값이 0이거나 2 이상인 수는 절대로 포함될 수 없다는 사실을 알 수 있다. 따라서

\[ \left( \bigcup_{p \,:\,prime} S(p,0) \right)^C = \{-1,1\}\]

결국 \( \{-1,1\}\)가 열린 집합이라는 뜻이 된다. 그러나 이는 위 성질 1에 모순된다. 따라서 소수는 무한하다.

리만 제타함수를 이용한 증명

함수 \( \zeta : (1, \infty ) \to \mathbb{R} \)를 아래와 같이 정의하자. 적분판정법에 의해 유효한 정의역임을 알 수 있다.

\[ \zeta (s) = \sum_{n=1}^{\infty} \frac {1}{n^s} \]

해당 급수식을 이용한 리만 제타함수의 정의역은 실수부가 1보다 큰 반평면으로 두는 것이 일반적이지만, 이 증명에선 불필요할 뿐더러 오히려 논증을 복잡하게 만들기 때문에 무시한다.

리만 제타함수와 소수 사이의 연관을 가장 잘 표현하는 정리는 오일러 무한곱이라고도 불리는 아래의 무한곱이다.

위 정리는 모든 자연수가 유일한 소인수분해를 가진다는 산술의 기본 정리에 기반한다. 따라서 증명의 주요 아이디어는 우변의 곱해지는 각 항을 \( \displaystyle \sum_{n=0}^{\infty} \frac{1}{p^{sn}} \)의 꼴로 바꾸고 무한곱에서 전개해 모든 자연수를 하나씩 만들어내는 것이다. 이 아이디어를 통한 정리의 엄밀한 증명은 아래에 있다.

여담으로 산술의 기본 정리는 소수의 무한성 없이 증명이 가능하므로 사용해도 된다.

pf)

어떤 자연수 \(N\)에 대해 \(N\) 이하의 소수들에 대한 유한 곱을 생각하자. 이때 무한곱에서 곱해지는 각 항들은 모두 1보다 크므로

\[ \prod_{p \leq N} \frac{1}{1-p^{-s}} \leq \prod_{p} \frac{1}{1-p^{-s}} \]

이때 수렴성이 보장되지 않았으니 무한대를 포함한 대소 관계를 사용한다.

그리고 \( N\)이하의 모든 자연수는 유일한 소인수분해를 가지고 가장 큰 소인수가 \( N\)을 넘지 못하므로 위 좌변의 유한곱을 전개했을 때 빠짐없이 한 번 씩 등장한다. 따라서

\[ \sum_{n=1}^{N} \frac {1}{n^s} \leq \prod_{p \leq N} \frac{1}{1-p^{-s}} \leq \prod_{p} \frac{1}{1-p^{-s}} \]

위 부등식에서 \( N\)을 무한대로 보내면

\[ \zeta(s) \leq \prod_{p} \frac{1}{1-p^{-s}} \]

반대로 \( \displaystyle \prod_{p \leq N} \frac{1}{1-p^{-s}}\)를 전개하면 \(N\)보다 큰 소인수를 가지는 자연수는 등장할 수 없으므로

\[ \prod_{p \leq N} \frac{1}{1-p^{-s}} \leq \sum_{n=1}^{\infty} \frac {1}{n^s}\]

그리고 \( N\)을 무한대로 보내면

\[ \prod_{p} \frac{1}{1-p^{-s}} \leq \sum_{n=1}^{\infty} \frac {1}{n^s}\]

두 부등식을 결합하면 해당 무한곱이 수렴하며 그 값이 \( \zeta(s)\)와 같음을 알 수 있다.

proved

사실 해당 보조 정리를 증명한 상황에서 소수의 무한성을 증명하는 것은 아주 쉽다. 소수가 유한하다고 가정하면 우변은 유한곱이 되고, 어떤 \(s\)를 고르든지 \(\displaystyle \prod_{i=1}^k \frac{p_i}{p_i-1}\)이라는 상한이 존재한다. 그러나 좌변의 리만 제타함수의 경우 적분 \(\displaystyle \int_1^{\infty} \frac{1}{x^s} dx \)와의 비교를 통해 \( s \to 1\)일 때의 상계가 존재하지 않음을 알 수 있다.

\[ \zeta(s) > \int_1^{\infty} \frac{1}{x^s} dx = \frac{1}{1-s} \to \infty \qquad as \qquad s \to 1^+ \]

아니면 \(s=2\)를 대입한 후에 소수가 유한하다면 \( \displaystyle \frac{\pi^2}{6} = \prod_{i=1}^k \frac{p_i^2}{p_i^2-1}\)가 유리수라는 식으로 모순을 이끌어낼 수 있다. 왜냐하면 린데만-바이어슈트라스 정리에 의해 \(\pi\)는 초월수이기 때문이다.

따라서 이 파트에선 소수의 무한성보다 더욱 강력한 명제를 증명할 것이다. 바로 \( \displaystyle \sum_p \frac{1}{p} \)가 발산한다는 사실이다. 2의 거듭제곱수가 무한히 많이 존재하지만 그들의 역수의 합은 1로 수렴하는 것처럼 소수의 무한성만으론 해당 급수의 발산을 보장할 수 없다. 그러나 반대로는 급수가 발산한다면 당연하게도 소수는 무한함을 알 수 있다.

먼저 \( \ln\)은 증가함수이므로 위 보조정리의 증명에서 양변에 \( \ln\)을 씌울 수 있고, 그 결과 다음을 얻는다.

\[ \ln \zeta (s) = - \sum_p \ln (1-p^{-s}) \]

로그는 일차함수로 간단하게 근사될 수 있음에 주목하자.

이 경우에는 특별하게 \( p \geq 2\)이고 \(s>1\)이므로 \( 0 < p^{-s} < \dfrac{1}{2}\)이고 아래 그래프를 보면

\( 0 < x < \dfrac{1}{2} \)일 때 \( -\ln (1-x) < 2x\)임을 알 수 있다. 미분을 통해 부등식을 엄밀하게 증명할 수도 있지만 당장은 생략한다.

따라서 임의의 \(s>1\)에 대해 아래 부등식이 성립한다. 적분판정법에 의해 아래에 등장하는 모든 식들은 수렴한다.

\[ \ln \zeta (s) = - \sum_p \ln (1-p^{-s}) < 2 \sum_p \frac{1}{p^s} \]

그리고 \(s>1\)이므로 \( \dfrac{1}{p^s} < \dfrac{1}{p} \)이다. 따라서 무한대를 포함한 대소 비교에서

\[ \sum_p \frac{1}{p^s} < \sum_p \frac{1}{p} \implies \frac{1}{2} \ln \zeta (s) < \sum_p \frac{1}{p} \]

따라서 합 \( \displaystyle \sum_p \frac{1}{p} \)가 수렴한다고 가정하면 그 값은 \(s>1\)에서의 \( \dfrac{1}{2} \ln \zeta (s)\)의 상계가 되고,

\[ \ln \zeta(s) > \ln \frac{1}{1-s} \]

에 의해 모순이 발생한다. 따라서 \( \displaystyle \sum_p \frac{1}{p} \)는 발산한다.