소수의 무한성

소수는 무수히 많이 존재한다.

정수론에서 가장 근본에 위치하는 기본적인 명제이면서 수학의 역사에서 가장 중요한 역할을 차지하는 결과물 중의 하나인 명제이다. 유클리드가 귀류법으로 증명한 이래 수많은 다양한 증명이 등장했는데, 피타고라스의 정리가 200가지가 넘는다해도 사실 많은 증명들은 다소 대동소이한 경우가 많은 반면 이쪽은 정말 그야말로 완벽히 다른 분야의 맥락에서 증명되는 경우도 많아 더 의미가 있다고 봄. 대부분 귀류법을 이용한 증명이고 귀류법은 그 증명 방법의 폭도 넓다보니… 여기서는 그 증명들 중 일부 눈여겨볼 만한 것들을 살펴보도록 한다. (183개의 증명을 모은 survey paper [1]의 도움을 받음. 일부는 책 Proofs from THE BOOK에서도 소개된 적이 있다)

  1. 유클리드의 증명. (대략 기원전 300년 이전) 소수의 개수가 유한하다고 가정하면 그 소수들의 곱에 1을 더한 것은 존재하는 모든 소수들과 서로 소이기 때문에 이 수의 소인수는 또 다른 새로운 소수가 되어야 하여 모순이다.
  2. 골드바흐의 증명. (1730) 페르마 수 F_n=2^{2^n}+1을 주목한다. F_n - 2 = 2^{2^n}-1 = (2^{2^{n-1}}+1)(2^{2^{n-1}}-1)=(2^{2^{n-1}}+1)(F_{n-1}-2)를 이용해 계속 인수분해하면 이 수가 곧 F_{n-1},F_{n-2},\ldots,F_0의 곱이 됨을 알 수 있다. 이들은 전부 홀수이므로 F_ni<n에 대해 F_i들과 전부 서로 소가 된다. 따라서 각각의 F_n의 최소의 소인수를 p_n이라고 하면 p_1,p_2,\ldots는 전부 서로 달라야 해서 무수히 많은 소수를 잡을 수 있게 된다. 이렇게 쌍마다 서로 소인 무한수열을 잡아서 그 소인수들이 무수히 많이 존재하게 되는 방식은 여러 배리에이션이 있다.
  3. 오일러의 증명. (1737) \displaystyle \frac{1}{1-\frac{1}{p^s}} = 1 + \frac{1}{p^s} + \frac{1}{p^{2s}}+\cdots로 쓸 수 있으므로, 이들을 모든 소수에 대해 곱해 전개하면 임의의 자연수 n에 대해 \frac{1}{n^s}가 정확히 한 번 등장한다. (소인수분해의 유일성) 즉 리만 제타 함수를 \displaystyle \zeta(s) = \sum_{n \geq 1} \frac{1}{n^s} = \frac{1}{(1-\frac{1}{2^s})(1-\frac{1}{3^s})(1-\frac{1}{5^s})\cdots}로 쓸 수 있게 된다. 여기서 \lim_{s \rightarrow 1+} \zeta(s) = \sum_{n \geq 1} \frac{1}{n} = +\infty로 발산함이 알려져 있으므로, 만약 소수가 유한하다면 리만 제타 함수의 곱 꼴로부터 위 극한값은 수렴해야해 모순을 얻는다.
  4. 리만 제타 함수를 이용한 또 다른 증명. (J. Hacks) 만약 소수가 유한하다면 리만 제타 함수에 2를 대입한 \zeta(2)는 유한한 유리수의 곱이 되어 유리수가 되어야 하는데, 1735년 오일러가 증명한 \zeta(2)=\frac{\pi^2}{6}이란 결과와(바젤 문제) 1794년 르장드르가 증명한 \pi^2가 무리수란 결과를 합하면 \zeta(2)는 무리수가 되어 모순을 얻는다.
  5. 비슷한 아이디어. 1943년 Bells가 AMM의 문제 코너에 출제한 문제로 \prod_{n \geq 1} (1-x^n)^{\mu(n)/n} = e^{-x}란 결과가 있다. 이 식은 |x|<1인 실수 x에 대해 성립하며 \mu는 정수론에서의 뫼비우스 함수. 그러면 x=-1/2를 대입 후 제곱해 정리하면 우변은 e가 되고 좌변은 \mu(n)의 값이 0이 아닌 n이 유한하게 나와야 해서 유한개의 유리수의 곱이 되어 유리수가 되지만 1815년 푸리에가 증명했듯 e는 무리수라서 모순을 얻는다.
  6. 한 편 Thue는 조합적으로 소수의 무한성을 증명했다. (1897) 소수의 유한성을 가정해 모든 소수를 p_1,\ldots,p_r로 둔다. 자연수 k에 대해 n=2k^2으로 두면 1+2k^2<2^{2k}임에서 양변을 k제곱하여 (n+1)^k<2^n임을 얻는다. 1 \leq m \leq 2^n인 어느 자연수 m을 임의로 택해 소인수분해한 결과를 p_1^{e_1}p_2^{e_2} \cdots p_r^{e_r}로 둔다. 여기서 r \leq k라고 가정합니다. 먼저 m \leq 2^n임에서 각각의 지수 e_i들은 전부 n보다 작거나 같고, 두 개가 동시에 n일 수는 없다. 따라서 n,k가 고정되어 있을 때 이러한 m을 잡는 경우의 수(=2^n)는 아무리 커도 (n+1)n^{r-1}보다 작거나 같을 수밖에 없다. 따라서 2^n \leq (n+1)n^{r-1}<(n+1)^r \leq (n+1)^k <2^n에 의해 모순이 나오게 되므로,r \geq k+1이 된다. 그런데 k는 임의로 잡은 자연수이므로 k=r로 설정하면 모순이 된다.
  7. 가장 흥미로운 증명 중 하나인 위상수학적 증명. (Fürstenberg, 1955) 정수 전체의 집합 \mathbb{Z}에서 a+bk꼴의 정수들을 모은 집합U_{a,b}들과 그 합집합들을 open set으로 설정한 토폴로지를 생각한다. (두 open set의 교집합 또한 open임을 확인해야 함) U_{a,b}의 여집합은 U_{0,b},U_{1,b}, \ldots,U_{b-1,b}U_{a,b}를 뺀 b-1개의 open set의 합집합이므로, U_{a,b}는 closed set이기도 하다. 이제 소수의 개수가 유한임을 가정하고 모든 소수 p에 대한 U_{0,p}들의 합집합을 잡아 A라 둔다. 각각의 U_{0,p}가 closed이므로 그 유한한 합집합인 A 역시 closed. 따라서 A의 여집합인 \{-1,1\}도 open이나, 이 토폴로지에서 open set은 반드시 무한집합이여야 해서 모순.
  8. 2015년 Alpoge는 van der Waerden’s theorem을 이용해 소수의 유한성을 가정하면 자연수들을 소인수분해했을 때의 지수들을 기우성을 토대로 컬러링을 잘 선택해 모순을 보이는 조합적인 풀이를 제시했다.[2]
  9. 2015년 Northshield는 한 줄짜리 귀류법 증명으로 \displaystyle 0 < \prod_{\text{prime }p} \sin \left( \frac{\pi}{p} \right) = \prod_{\text{prime }p} \sin \left( \frac{\pi(1+2\prod_{\text{prime }q}q)}{p} \right) =0제시했는데 기본적으로 유클리드의 증명을 rephrase한 것이라 볼 수 있다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/10/07)

References

[1] R. Meštrović, “Euclid’s Theorem on The Infinitude of Primes: A Historical Survey of Its Proofs (300 B.C.-2017)” arXiv preprint arXiv:1202.3670v3

[2] L. Alpoge, “van der Waerden and the primes” American Mathematical Monthly, 122:8, 784-785, DOI: 10.4169/amer.math.monthly.122.8.784

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중