[퍼온글] 베르트랑 공준 (Betrand Postulate)과 그 증명

※ 출처 - http://kevin0960.tistory.com/

베르트랑의 공준에 따르면 $2$ 이상의 자연수 $n$에 대하여, $n < p < 2n$을 만족하는 소수 $p$가 반드시 존재한다. 이는 최초로 체비셰프(Chebyshev)에 의해 증명되었으나 그의 증명은 매우 길고 복잡하였다. 왜냐하면 체비셰프의 증명은 다른 문제를 해결함으로써 파생된 결과 이였기 때문이다. 후에 인도의 수학자 라마누잔(Ramanujan)이 쳬비셰프의 방법 보다 훨씬 간단한 방법으로 증명하였다. 하지만 나중에 폴 에르디시(Paul Erdős)가 기초적인 수학만을 사용하여 간결하게 증명하였는데, 여기 소개하고자 할 증명은 바로 폴 에르디시의 증명이다.  

정리. 베르트랑의 공준, 체비셰프의 정

$2$ 이상의 자연수 $n$에 대하여, $n < p < 2n$을 만족하는 소수 $p$가 반드시 존재한다.

이 문제에 대해서는 보조정리가 4개 필요하다.

보조정리 (1)

모든 양의 정수 n 에 대하여 아래의 식이 성립한다. \[ \frac {4^n}{2n+1} < \binom{2n}{n} \]

증명. 먼저 이항정리에 의해 \[ 4^n = (1+1)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} \] 그런데, $\binom{2n}{n}$이 위 식의 두변의 항들 중 가장 큰 항이므로, \[ 4^n= \sum_{k=0}^{2n} \binom{2n}{k} < (2n+1) \binom{2n}{n} \quad \Rightarrow \quad \frac{4^n}{2n+1} < \binom{2n}{n} \] 따라서 부등식이 성립한다..

보조정리 (2)

고정된 소수 $p$에 대하여 $R(p,\, n)$을 $p^r$이 $\binom{2n}{n}$을 나누게 하는 $r$ 중에 가장 큰 수라 정의하자. 그러면, $p^{R(p,n)} \leq 2n$이 성립한다.

증명. 고정된 소수 $p$에 대하여 $p^r$이 $n!$을 나누게 하는 $r$ 중에 가장 큰 수는 \[ \sum_{i=1}^{\infty} \left\lfloor \frac {n}{p^{i}} \right\rfloor \] 로 정의할 수 있음이 알려져 있다. (단, $\lfloor x \rfloor$은 $x$를 넘지 않는 가장 큰 정수이다.) 따라서 \[ R(p,\, n) = \sum_{k=1}^{\infty} \left\lfloor \frac{2n}{p^{k}} \right\rfloor - 2\sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^{k}} \right\rfloor = \sum_{k=1}^{\infty} \left( \left\lfloor \frac{2n}{p^{k}} \right\rfloor - 2\left\lfloor \frac{n}{p^{k}} \right\rfloor \right) \] 그런데, $k > \log_p(2n)$이면, 위 시그마 항들이 모두 $0$이 된다. 또한, \[ \left\lfloor \frac{2n}{p^{k}} \right\rfloor - 2\left\lfloor \frac{n}{p^{k}} \right\rfloor = 0 \text{ or } 1 \] 이므로, $R(p,\, n) \leq \log_p(2n)$임을 알 수 있다. 따라서, \[ p^{R(p,\, n)} \le p^{\log_p (2n)} \leq 2n \] 즉, 원하는 부등식을 얻게 된다..

보조정리 (3)

$n \geq 5$라 하자. 그러면

• $p > \sqrt{2n}$인 모든 소수 $p$에 대하여 $R(p,\,n) \leq 1$이 성립한다.
• $\frac{2n}{3} < p \leq n$인 모든 소수 $p$에 대해서 $R(p,\,n) = 0$이 성립한다.

증명. 먼저 $p > \sqrt{2n}$이라 가정하자. 그러면 보조정리 (2)에 의해 \[ R(p,\, n) \leq \log_p(2n) < \log_{\sqrt{2n}}(2n) = 2 \] 따라서 $R(p,\,n) \leq 1$임을 확인할 수 있다.

$ $

이제 $\frac{2n}{3} < p \leq n$라 가정하자. 그러면 $\frac{1}{n} \leq \frac{1}{p} < \frac{3}{2n}\,$을 얻고, 이를 이용하면 \[ \left\lfloor \frac{2n}{p} \right\rfloor = 2, \quad \left\lfloor \frac{n}{p} \right\rfloor = 1, \quad \left\lfloor \frac{2n}{p^{k}} \right\rfloor = 0m \quad \left\lfloor \frac{2n}{p^{k}} \right\rfloor = 0 \quad (k \geq 2) \] 임을 간단히 확인할 수 있다. 따라서 \[ R(p,\, n) = \sum_{k=1}^{\infty} \left\lfloor \frac{2n}{p^{k}} \right\rfloor - 2\sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^{k}} \right\rfloor = 2 - 2 \cdot 1 = 0 \] 이므로 보조정리가 성립한다..

보조정리 (4)

아래와 같이 소수곱 함수(primorial) 를 정의하자. \[ 1\# = 1, \quad n\# = \prod_{p \leq n} p \] 이 때, $1$ 보다 큰 모든 자연수 $n$에 대하여 $n\# < 4^n$이 성립한다.

증명. 수학적 귀납법으로 보이자. 먼저 $n=1,\,2$인 경우 \[ 1\# = 1 < 4^1, \quad 2\# = 2 < 4^2 \] 이므로 보조정리가 성립한다. 이제 $(n-1)$ 이하의 모든 자연수에 대해 보조정리가 성립한다고 가정하자.

1. $n$이 짝수 일 때, $n > 2$ 이고, 짝수인 소수는 $2$가 유일하므로 \[ n\# = (n-1)\# < 4^{n-1} < 4^n \]이 되어 $n$인 경우에도 보조정리가 성립한다.
2. $n$이 홀수 일 때, $n = 2m + 1$이라고 하자. (단, $m$은 자연수) 그러면 \[ \begin{aligned} 4^m &= \frac{1}{2}\,(1+1)^{2m+1} = \frac{1}{2} \sum_{k=0}^{2m+1} \binom{2m+1}{k} \\ &> \frac{1}{2} \left( \binom{2m+1}{m} + \binom{2m+1}{m+1} \right) = \binom{2m+1}{m+1} \end{aligned} \]또한 $m + 2 \leq p \leq 2m + 1$ 인 모든 소수 $p$에 대하여 아래를 만족한다. \[ p \mid \binom{2m+1}{m+1} \]따라서, \[ \frac{(2m+1)\#}{(m+1)\#} = \prod_{p = m+2}^{2m+1}p < \binom{2m+1}{m+1} < 4^m \]결과적으로 귀납가정과 위 부등식에 의해서 아래의 식이 얻는다. \[ n\# = (2m+1)\# = \frac{(2m+1)\#}{(m+1)\#} \times (m+1)\# < 4^m \times 4^{m+1} = 4^{2m+1} = 4^n \]따라서 $n$인 경우에도 보조정리가 성립한다.

따라서 수학적 귀납법에 의하여 모든 자연수 $n$에 대하여 보조정리가 성립한다..

체비셰프 정리(Chebyshev's Theorem)의 증명

증명. 증명은 귀류법을 이용하자. 일단, $n \leq 2048$ 일 때, $3$, $5$, $7$, $13$, $23$, $43$, $83$, $163$, $317$, $631$, $1259$, $2503$에 의해 성립한다. 따라서, $n > 2048$인 경우만을 살펴보아도 충분하다. 우선 $2048$ 보다 큰 자연수 $n$이 존재하여, $n < p < 2n$을 만족하는 소수가 존재하지 않는다고 가정해보자. 그리고 나서 아래의 조건을 만족하는 소수 $p$를 생각하자. \[ p \mid \binom{2n}{n} \tag*{($\ast$)} \] 그러면 이러한 소수 $p$는 아래의 조건들을 만족하지 않는다.

1. $p \geq 2n$; 우선 $p > 2n$일 수는 없고, $p = 2n$이면 $p$가 소수라는 사실에 모순이다.
2. $n < p < 2n$; 가정의 의해 $n < p < 2n$인 소수 $p$는 존재하지 않는다.
3. $\frac{2n}{3} < p \leq n$; 보조정리 (3)에 의해 알 수 있다.

따라서, $(\ast)$를 만족하는 소수 $p$는 $p \leq \frac{2n}{3}\,$이어야만 한다. 이 때, 보조정리 (2)에 의해 다음과 같이 될 수 있다. \[ \binom{2n}{n} = \left( \prod_{p \leq \sqrt{2n}} p^{R(p,\,n)} \right) \left( \prod_{\sqrt{2n} < p \leq \frac{2n}{3}} p^{R(p,\,n)} \right) < (2n)^{\sqrt{2n}} \left( \prod_{\sqrt{2n} < p \leq \frac{2n}{3}} p^{R(p,\,n)} \right) \] 또한 보조정리 (1)에 의해 \[ \frac{4^n}{2n+1} < \binom{2n}{n} \] 이고 보조정리 (3)과 보조정리 (4)에 의해 \[ \left( \prod_{\sqrt{2n} < p \leq \frac{2n}{3}} p^{R(p,n)} \right) \leq \left\lfloor \frac{2n}{3} \right\rfloor \# < 4^{\left\lfloor \frac{2n}{3}\, \right\rfloor} \] 따라서, 위 세 식에 의해 다음이 성립한다. \[ \frac{4^n}{2n+1} < (2n)^{\sqrt{2n}} 4^{\left\lfloor \frac{2n}{3}\, \right\rfloor} < (2n)^{\sqrt{2n}} 4^{\frac{2n}{3}} \] 위 식을 정리하면 \[ 4^{\frac{n}{3}} < (2n+1)(2n)^{\sqrt{2n}} < (2n)^2(2n)^{\sqrt{2n}} = 2n^{2+\sqrt{2n}} < 2n^{\frac{4\sqrt{2n}}{3}} \] 그러므로 $4^{\frac{n}{3}} < 2n^{\frac{4\sqrt{2n}}{3}}$을 얻는다. 이제 양변에 로그를 취하면 \[ \frac{n}{3}\, \log 4 < \frac{4\sqrt{2n}}{3}\, \log (2n) \] 다시 양변을 정리하면 $\sqrt{2n} \log 2 < 4 \log (2n)$을 얻는다. 때, $2n = 2^{2t}$로 치환한 후 정리하면 \[ 2^t \log 2 < 8t\log 2 \quad \Rightarrow \quad 2^t < 8t \quad \Rightarrow \quad t < 6 \] 따라서, $n < \frac{2^{12}}{2} = 2048$. 이는 위에서 $n > 2048$이라 가정한데에 모순이다. 따라서, 귀류법에 의해 $2$ 이상의 모든 자연수 $n$에 대해서, $n < p < 2n$ 을 만족하는 소수 $p$가 언제나 존재한다..