Introduction
소수(prime number)가 무한하다는 것은 매우 잘 알려진 사실이다. 문제는 어떻게 그 사실을 보일 것이냐는 것이다. 이 포스트에서는, 소수가 무한하다는 사실을 증명하는 알려진 여러 방법들을 살펴보기로 한다.
Euclid’s Proof (B.C.300)
$p_1=2$, $p_2=3$, $\cdots$로 $p_i$들은 증가하는 소수의 수열이라고 하자. 만약 소수가 유한하다면 최대의 소수 $p_n$이 존재한다. 이제 모든 소수들의 곱에 1을 더한 숫자 $P=p_1\cdot p_2\cdots p_n+1$이라고 두자. 그러면 $P$는 $p_1$, $p_2$, $\cdots$, $p_n$중 어떤 수로도 나누어 떨어지지 않는다. $P$를 나누는 수를 하나 가져와서 $q$라고 하자. 그러면 $q$는 $p_1$, $p_2$, $\cdots$, $p_n$중 어떤 수도 될 수 없는데, 이는 $P-p_1\cdot p_2\cdots p_n=1$이기 때문이다. 따라서 이 $q$는 새로운 소수이고, $p_1$, $p_2$, $\cdots$, $p_n$는 모든 소수들의 집합이라는 가정에 모순이 생긴다.
Kummer’s Restatement of Euclid’s Proof
유클리드의 증명과 같은 세팅 하에서, $N=p_1\cdot p_2\cdots p_n$이라고 하자. 그러면 $N-1$이라는 자연수는 $N$과 같은 소인수를 하나도 가질 수 없다(왜냐하면 $N-(N-1) = 1$이기 때문). 따라서 $N-1$을 나누는 소수 $p_r$은 $p_1$, $p_2$, $\cdots$, $p_n$들중에 존재하지 않고, 이는 $p_1$, $p_2$, $\cdots$, $p_n$가 모든 소수들의 집합이라는 것에 모순이다. 따라서 소수는 무한하다.
Goldbach’s proof (1750)
보조정리
- 페르마 정수 $F_n = 2^{2^{n}}+1$들 중 아무거나 두 개를 가져오면 이들은 서로소이다.
이제 보조정리를 사용하여 소수가 무한하다는 것을 증명하면,
각 페르마 정수 $F_n$의 소인수 $p_n$을 가져오자. 보조정리에 의해서 우리는 이 소인수들은 모두 다르다는 것을 알고, 따라서 소수는 무한하다.
Furstenberg’s Topological Proof (1955)
먼저 정수집합 $\mathbb{Z}$위에 위상공간 $(\mathbb{Z}, T_{\mathbb{Z}})$를 하나 만들자. 이 위상공간의 열린 집합(open set)은 공집합 $\emptyset$과
\[S(a,b) = \{an + b | n\in\mathbb{Z}\} = a\mathbb{Z} + b\]들의 합집합으로 정의된다.
이렇게 정의하면 이 공간이 위상공간이 됨을 쉽게 확인할 수 있다.
이 집합은 크게 두 가지의 성질을 갖는다.
- Finite set은 open일 수 없다 : 모든 open set들은 infinite set $S(a,b)$의 합집합이기 때문. 다른 말로 하면, 유한집합의 여집합은 closed일 수 없다.
- Basis set $S(a,b)$는 clopen set이다 : 이는 다음처럼 기술될 수 있다.
또한 다음 중요한 성질이 성립한다. 모든 소수의 배수로 표현될 수 없는 수들은 +1과 -1뿐이므로,
\[\mathbb{Z} - \{1,-1\} = \cup_{p\text{ is prime}} S(p,0)\]따라서, 바로 위 식의 좌변은 closed일 수 없다. 반면에, 우변의 $S(p,0)$은 closed이다. 따라서, 만약 소수가 유한하다면 finite union of closed set인 우변 때문에 좌변도 closed여야 한다. 이는 가능하지 않으므로, 소수는 무한하다.
Filip Saidak’s Proof
$n>1$을 양의 정수라 하자. $n$과 $n+1$은 연속된 정수이므로, 서로소이다. 따라서 다음 수 $N_2 = n(n+1)$은 두 개의 소인수를 가진다. 비슷하게, $N_2$와 $N_2+1$또한 서로소이므로
$N_3 = N_2(N_2+1) = n(n+1)(n(n+1)+1)$는 세개의 소인수를 가진다.
이 과정은 무한히 반복될 수 있으므로, 소수는 무한하다.