베르트랑 공준

베르트랑 공준 

모든 자연수 $n$에 대하여, $n < p \le 2n$을 만족하는 소수 $p$가 존재한다.

 

증명 

크게 7단계로 나누었다.

 

Step 1. $n \le 4000$에 대하여 베르트랑의 공준이 성립함을 실험적으로 확인하자. 바로 앞의 소수의 $2$배보다 작은 소수들의 수열 $$2, 3, 5, 7, 13, 23, 43, 83, 163,$$ $$317, 631, 1259, 2503, 4001$$이 존재한다. 따라서 $n\le 4000$에 대하여 구간 $\left( n,2n \right]$은 위의 $14$개의 소수들 중 하나를 포함하므로, 베르트랑의 공준이 성립한다.

 

Step 2. $2$ 이상인 자연수 $a$에 대하여 $a+1<2^a$가 성립함을 증명하자.

증명은 수학적 귀납법을 이용한다. $a=2$일 때 $3<4$이므로 성립한다. $a=n$일 때 성립 가정하면 $a=n+1$일 때는 $n+1+1<2^n+1<2^n+2^n=2^{n+1}$이므로 주어진 부등식이 $2$ 이상의 자연수 $a$에 대하여 성립함이 증명되었다.

 

Step 3. 모든 실수 $x \ge 2$에 대하여 부등식 $$\displaystyle\prod_{p\le x}p \le 4^{x-1}$$이 성립함을 증명하자. (좌변은 $x$ 이하의 모든 소수들의 곱을 의미한다.)

실수 $x$에 대하여 증명하는 것이지만, 범위를 좁혀 자연수 $x$에 대해서 증명해도 충분하다. 왜냐하면 $\lfloor x \rfloor = m$라 하면, $$\displaystyle\prod_{p\le x}p = \displaystyle\prod_{p\le m}p \le 4^{m-1} \le 4^{x-1}$$이기 때문이다.

여기서 증명 범위를 더 줄일 수 있다. 자연수 $x$를 넘지 않는 가장 큰 소수를 $q$라 하면, $$\displaystyle\prod_{p\le x}p=\displaystyle\prod_{p\le q}p \le 4^{q-1} \le 4^{x-1}$$이므로, 소수 $x$에 대해서만 증명해도 충분하다. $x=2$이면 $2 \le 4$이므로, 홀수인 소수 $x=2m+1$에 대해서만 주어진 부등식이 성립함을 증명하자.

그 전에, 다음 식을 증명하고 가자. $$\displaystyle\prod_{m+1<p\le 2m+1}p \le {2m+1 \choose m} \le 2^{2m}$$

먼저 첫 번째 부등호부터 이해해보자. 좌변인 $m+1$ 초과 $2m+1$ 이하의 모든 소수들의 곱을 $P$라고 하고, 우변인 $\frac{(2m+1)!}{m!(m+1)!}$을 $n$이라고 하자. 이때, 분자인 $(2m+1)!$은 $2m+1$ 이하의 모든 자연수의 곱이므로 $P$의 배수이지만, 분모인 $m!(m+1)!$은 $m+1$ 이하의 자연수들만의 곱이므로 $P$의 배수가 될 수 없다. 따라서 $(2m+1)!=a$, $m!(m+1)!=b$라고 하면, $P \nmid b$이고, $P \mid a=nb$이므로 $P \mid n$이다. 따라서, 좌변은 우변의 약수이므로, $P \le n$이 성립한다.

다음으로 두 번째 부등호를 이해해보자. 이항 계수 항등식 $$\displaystyle\sum_{k=0}^{n}{n \choose k}=2^n$$에서, 다음을 얻는다. $$\begin{eqnarray} 2{2m+1 \choose m} && ={2m+1 \choose m}+{2m+1 \choose m+1} \\&& \le \displaystyle\sum_{k=0}^{2m+1}{2m+1 \choose k}=2^{2m+1} \end{eqnarray}$$ 양변을 2로 나누면 두 번째 부등호가 성립함을 알 수 있다.

이제 원래 부등식을 증명할 수 있다. 증명은 강한 수학적 귀납법을 이용한다. $x=2,3,\cdots,2m$에 대하여 주어진 부등식이 성립한다고 가정하자. 이제, $x=2m+1$일 때 주어진 부등식이 성립함을 증명하자. 주어진 부등식의 곱을 나누어 써보면 $$\displaystyle\prod_{p \le 2m+1} p=\displaystyle\prod_{p \le m+1}p \times \displaystyle\prod_{m+1<p \le 2m+1}p$$ 이때 가정에 의하여 $$\displaystyle\prod_{p\le 2m+1}p \le 4^m$$이고, 앞에서 증명한 부등식에 의하여 $$\displaystyle\prod_{m+1<p\le 2m+1}p \le 2^{2m}=4^m$$이므로, $$\displaystyle\prod_{p\le 2m+1}p \le 4^m 4^m=4^{2m}$$이 성립한다.

 

Step 4. 르장드르의 정리에 의하면, 자연수 ${2n \choose n}=\frac{2n!}{n!n!}$은 소인수 $p$를 정확히 $$\displaystyle\sum_{k \ge 1}\left(\lfloor\dfrac{2n}{p^k}\rfloor-2\lfloor\dfrac{n}{p^k}\rfloor\right)$$번 포함함을 알 수 있다. 분모에 르장드르의 정리를 적용하여 얻은 수에, 분자에 르장드르의 정리를 적용하여 얻은 수를 빼주면 된다. 여기서 $\sum$ 안의 각 항은 정수이면서 부등식 $$0\le \dfrac{2n}{p^k}-2\left( \dfrac{n}{p^k}-1 \right)=2$$을 만족하기 때문에 $0$ 또는 $1$이다. 또한, $p^k>2n$이면 각 항은 $0$이다. 따라서 ${2n \choose n}$은 $p$를 정확히 $$\displaystyle\sum_{k \ge 1}\left(\lfloor\dfrac{2n}{p^k}\rfloor-2\lfloor\dfrac{n}{p^k}\rfloor\right)\le\,_\max\left\{r\mid p^r\le 2n\right\}$$번 포함한다. 그러므로 ${2n \choose n}$을 나누면서 가장 큰 지수 $r$을 갖는 멱수 $p^r$은 $2n$보다 클 수 없다. 특히, $\sqrt{2n}$보다 큰 소수들은 ${2n \choose n}$에 기껏해야 한 번만 나타난다.

 

Step 5. $\frac{2}{3}n<p\le n$인 소수 $p$는 절대로 ${2n \choose n}$의 약수가 될 수 없다. ($n \ge 3$, 즉 $p \ge 3$인 경우) 왜냐하면, $3p>2n$이면, $\frac{(2n)!}{n!n!}$의 분자에 포함된 $p$의 배수는 $p$와 $2p$ 뿐인데, 분모는 소인수로써 $p$를 두 번 포함하기 때문이다.

 

Step 6. ${2n \choose n}$을 살펴보면, $p \le \sqrt{2n}$인 소수들은 여러 번 곱해지고, $\sqrt{2n}<p\le\frac{2}{3}n$인 소수들은 많아야 한 번만 나타나고, $\frac{2}{3}n<p\le n$인 소수들은 한 번도 곱해지지 않고, $n<p\le 2n$인 소수들은 분자에만 있으므로 한 번씩 곱해진다. 이를 토대로 다음을 얻는다. $${2n \choose n}\le\displaystyle\prod_{p\le\sqrt{2n}}p\times\displaystyle\prod_{\sqrt{2n}<p\le\frac{2}{3}n}p\times\displaystyle\prod_{n<p\le 2n}p$$ 이때, 이항 계수의 하계를 대입하면 다음을 얻는다. $$\dfrac{4^n}{2n}\le\displaystyle\prod_{p\le\sqrt{2n}}p\times\displaystyle\prod_{\sqrt{2n}<p\le\frac{2}{3}n}p\times\displaystyle\prod_{n<p\le 2n}p$$ $p\le\sqrt{2n}$을 만족하는 소수의 개수는 $\sqrt{2n}$보다 작거나 같으므로, 최종적으로 $n \ge 3$에 대하여 다음이 성립한다. $$4^n\le(2n)^{1+\sqrt{2n}}\times\displaystyle\prod_{\sqrt{2n}<p\le\frac{2}{3}n}p\times\displaystyle\prod_{n<p\le 2n}p$$

 

Step 7. 이제 임의의 $n$에 대하여 $n<p\le 2n$을 만족하는 소수 $p$가 존재하지 않는다고 가정하자. 그러면, Step 6. 에서 최종적으로 얻은 부등식의 마지막 항이 $1$이 된다는 사실과 Step 3. 에서 증명한 부등식을 이용하여 다음을 얻는다. $$4^n\le(2n)^{1+\sqrt{2n}}\times 4^{\frac{2}{3}n}$$ 즉, $n \ge 3$에 대하여 $$4^{\frac{1}{3}n}\le(2n)^{1+\sqrt{2n}}$$이 성립되어야 한다. 그런데 이 부등식은 $n$이 증가할 때 좌변의 증가 속도가 우변보다 훨씬 빠르다. (좌변은 $n$제곱인데, 우변은 $\frac{1}{2}n$이기 때문이라고 해석할 수 있다.) 즉, 충분히 큰 $n$에 대하여 위의 부등식은 성립하지 않는다. 이제 부등식이 성립하지 않게 되는 $n$을 구해보자.

Step 2. 의 부등식을 이용하면 $$\begin{eqnarray}2n&&=(\sqrt[6]{2n})^6<(\lfloor\sqrt[6]{2n}\rfloor+1)^6\\&&<2^{6\lfloor\sqrt[6]{2n}\rfloor}\le 2^{6\sqrt[6]{2n}}\end{eqnarray}$$이 성립함을 알 수 있고, 따라서 $n \le 50$일 때 ($18 \ge 2\sqrt{2n}$일 때) 위의 두 부등식을 연립하면 다음 부등식을 얻는다. $$\begin{eqnarray}2^{2n} && \le (2n)^{3(1+\sqrt{2n})}<2^{\sqrt[6]{2n}(18+18\sqrt{2n})}\\&&<2^{20\sqrt[6]{2n}\sqrt{2n}}=2^{20(2n)^\frac{2}{3}}\end{eqnarray}$$ 즉, $2n\le 20(2n)^\frac{2}{3}$이므로 $(2n)^\frac{1}{3}<20$을 의미한다. 따라서, $n<4000$을 얻는다. 이는 Step 1. 에 모순이므로 베르트랑 공준이 증명되었다.   $\blacksquare$

 

Exponential 17 김지하