체비셰프의 정리 (베르트랑 공준, Betrand Postulate)

체비셰프

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

체비셰프의 정리
2 이상의 모든 자연수 n 에 대해서, n < p < 2n 을 만족하는 소수 p 가 존재한다.

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

보조정리 1)
모든 양의 정수 n 에 대하여 아래의 식이 성립한다.

$eq=\frac {4^n}{2n+1} < \binom {2n}{n}$

증명)
일단, 이항정리에 따라

$eq=4^n = (1+1)^{2n} = \sum_{k=0}^{2n}\binom {2n}{k}$

그런데, $eq=\binom {2n}{n}$ 이 위 항들 중 가장 큰 항이므로,

$http://www.sitmo.com/gg/latex/latex2png.2.php?z=100&eq=4%5En%3D%20%5Csum_%7Bk%3D0%7D%5E%7B2n%7D%5Cbinom%7B2n%7D%7Bk%7D%20%3C%20(2n%2B1)%20%5Cbinom%7B2n%7D%7Bn%7D%20%5C%5C%20%5Ctherefore%20%5Cfrac%7B4%5En%7D%7B2n%2B1%7D%20%3C%20%5Cbinom%7B2n%7D%7Bn%7D%20~~~~~~~~~~~~~~~~~~$

□

보조정리 2)
R(p,n) 을 아래와 같이 정의하자.

$eq=R(p,n) = x, ~p^x ~|| ~\binom{2n}{n}$

이 때, 다음이 성립한다.

$eq=p^{R(p,n)} \le 2n$

증명)

$eq=R(p,n) = \sum_{k=1}^{\infty}[\frac{2n}{p^k}] - 2 \sum_{k=1}^{\infty} [\frac{n}{p^k}]\ = \sum_{k=1}^{\infty}([\frac{2n}{p^k}] - 2[\frac{n}{p^k}])$

그런데,

$eq=k > log_p(2n)$

이면, 위 시그마 항들이 모두 0 이 된다. 또한,

$eq=[\frac{2n}{p^k}] - 2[\frac{n}{p^k}] = 0 ~or ~1$

이므로, 전체의 합은

$eq=R(p,n) = \sum_{k=1}^{\infty}([\frac{2n}{p^k}] - 2[\frac{n}{p^k}]) \le log_p(2n)$

따라서,

$eq=p^{R(p,n)} \le p^{log_p (2n)} \le 2n$

□

보조정리 3)

p > \sqrt{2n}인 모든 소수 p 에 대해서 다음이 성립한다.

$eq=R(p,n) = [\frac{2n}{p}] - 2[\frac{n}{p}]$

증명) 조건에 따라,

$http://www.sitmo.com/gg/latex/latex2png.2.php?z=100&eq=p%5E2%20%3E%202n%20%5Crightarrow%20%5Csum_%7Bk%3D2%7D%5E%7B%5Cinfty%7D(%5B%5Cfrac%7B2n%7D%7Bp%5Ek%7D%5D%20-%202%5B%5Cfrac%7Bn%7D%7Bp%5Ek%7D%5D)%20%3D%200%20$

이므로 성립. □

보조정리 4)
아래와 같이 소수곱 함수(primorial) 를 정의하자.

$eq=\theta (n) = \prod_{p \le n} p,~ \theta(1) = 1$

이 때, 1 보다 큰 모든 자연수 n 에 대해 다음이 성립한다.

$eq=\theta (n) < 4^n$

증명)
수학적 귀납법으로 보이자.
i) n = 1, 2;

$eq=\theta(1) = 1 < 4^1 ,~ \theta(2) = 2 < 4^2$

이므로 성립.
ii) (n- 1) 이하의 모든 자연수에 대해 성립을 가정하자

n 이 짝수 일 때;

n > 2 이고, 짝수인 소수는 2 가 유일하므로

$eq=\theta(n) = \theta(n-1) < 4^{n-1}<4^n$

이므로 성립

n 이 홀수 일 때;

n = 2m + 1 이라고 하자 . (단, m 은 자연수)

$eq=4^m = \frac{1}{2}(1 +1)^{2m+1} = \frac{1}{2}\sum_{k=0}^{m}\binom{2m+1}{k} \\ > \frac{1}{2} (\binom{2m+1}{m} + \binom{2m+1}{m+1} = \binom{2m+1}{m}$

이 때, m + 1 < p < 2m + 2 인 모든 소수 p 에 대해 아래를 만족한다.

$eq=p~ | ~\binom{2m+1}{m}$

따라서,

$eq=\frac{\theta(2m+1)}{\theta(m+1)} = \prod_{p > m+1}^{p <2m+1}p < \binom{2m+1}{m} < 4^m$

결과적으로 귀납가정과 위에 의해서 아래의 식이 만족한다.

$eq=\theta(2m+1) = \frac{\theta(2m+1)}{\theta(m+1)}\times \theta(m+1) < 4^m \times 4^{m+1} = 4^{2m+1}$

□

보조정리 5)
우리는 다음의 것들을 증명없이 이용하도록 하겠다. (증명이 워낙 간단하므로)

$eq=n >5 ~\rightarrow~ \frac{2n}{3} >\sqrt{2n}$

$eq=n > 0~ \rightarrow ~2n +1 <(2n)^2$

$eq=n > 18~ \rightarrow ~2 < \frac{\sqrt{2n}}{3}$

$eq=2^t <8t ~ \rightarrow ~ t <6$

체비셰프 정리 증명)

이번 증명에서는 귀류법을 이용하자. 일단, n ≤ 2048 일 때, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503 에 의해 성립. 따라서, n > 2048 일 때를 살펴보자.

어느 2048 보다 큰 임의의 자연수 n 에 대해, n < p < 2n 을 만족하는 소수가 존재하지 않음을 가정하자.

이 때, 아래의 조건을 만족하는 소수 p 를 생각하자.

$eq=p~|~\binom{2n}{n}$

따라서, 이러한 소수 p 는 아래의 조건들을 만족하지 않는다.

p ≥ 2n ; 왜냐하면 p | (2n)! 이고, p = 2n 이면 모순이므로 (왜냐하면 n 이 2049 이상)
n < p < 2n ; 왜냐하면 가정의 의해 n < p < 2n 인 소수 p 는 존재하지 않으므로.
2n / 3 < p ≤ n; 만약, 이를 만족하는 소수 p 가 존재한다고 하면, n / p ≥ 1, 2n / p < 3 이고 , 보조정리 5 - 1 에 의해 p > \sqrt{2n} 이므로 보조정리 3 에 의해

$eq=R(p,n) = [\frac{2n}{p}] -2[\frac{n}{p}] \le 2 - 2 = 0$

이므로 p | \binom{2n}{n} 를 만족하는 소수 p 가 존재하지 않는다.

따라서, p | \binom{2n}{n}를 만족하는 모든 소수 p 는 p ≤ 2n / 3 을 만족한다.

이 때, 보조정리 2 에 의해 다음과 같이 될 수 있다.

$eq=\binom{2n}{n} = (\prod_{p = 2}^{p \le \sqrt{2n}}p^{R(p,n)} )(\prod_{p > \sqrt{2n}}^{p \le \frac{2n}{3} }p^{R(p,n)} ) < (2n) ^{\sqrt{2n}} (\prod_{p > \sqrt{2n}}^{p \le \frac{2n}{3} }p^{R(p,n)} )$

또한, 보조정리 1 에 의해

$eq=\frac{4^n}{2n+1} < \binom{2n}{n}$

이고, 보조정리 4 에 의해

$eq= (\prod_{p > \sqrt{2n}}^{p \le \frac{2n}{3} }p^{R(p,n)} ) < (\prod_{p = 2}^{p \le \frac{2n}{3} }p^{R(p,n)} ) = \theta([\frac{2n}{3}])$

따라서, 위 세 식에 의해 다음이 성립한다.

$eq=\frac{4^n}{2n+1} < (2n)^{\sqrt{2n}} \times \theta([\frac{2n}{3}]) < (2n)^{\sqrt{2n}} \times 4^{[\frac{2n}{3}]} < (2n)^{\sqrt{2n}} \times 4^{\frac{2n}{3}}$

위 식을 정리하면

$eq=4^{\frac{n}{3}} < (2n+1)(2n^{\sqrt{2n}})$

이 때, 보조정리 5 - 2,3 에 의하여

$eq=(2n+1)(2n^{\sqrt{2n}}) < (2n)^2(2n^{\sqrt{2n}}) = 2n^{2+\sqrt{2n}} < 2n^{\frac{4\sqrt{2n}}{3}}$

$eq=\therefore~ 4^{\frac{n}{3}} < 2n^{\frac{4\sqrt{2n}}{3}}$

양변에 로그를 취하면

$eq=\frac{n}{3}\log n< \frac{4\sqrt{2n}}{3} \log 2n$

다시, 양변을 정리하면

$eq=\sqrt{2n} \log 2 < 4 \log 2n$

이 때, 2n 을 2^{2t} 으로 치환한 후, 보조정리 5 -4 에 의해,

$eq=2^t \log 2 < 8t\log 2 \\ \therefore~ \frac{ 2^t }{t} < 8 \rightarrow t < 6$

따라서,

$eq=n < \frac{2^{12}}{2} = 2048$

이는 위에서 n > 2048 이라 한 데에 모순이다. 따라서, 귀류법에 의해 2 이상의 모든 자연수 n에 대해서, n < p < 2n 을 만족하는 소수 p 가 존재한다.

'Mathematics' 카테고리의 다른 글

고차 방정식의 해 구하기 (뉴튼 - 랩슨법, Newton-Rahpson Method) (9)	2009.09.27
정다면체는 왜 5 개 밖에 없는가? (20)	2009.07.17
라그랑즈의 네제곱수 정리와 그 증명(Four square theorem) (4)	2009.04.19
3차방정식의 근의 공식( 카르다노의 해법) 과 판별식 (21)	2009.04.19
4차 방정식(Quartic Equation)의 페라리의 해법과 근의 공식 (4)	2008.08.09

나의 휴식터

체비셰프의 정리 (베르트랑 공준, Betrand Postulate)

'Mathematics' 카테고리의 다른 글

티스토리툴바

체비셰프의 정리 (베르트랑 공준, Betrand Postulate)

'Mathematics' 카테고리의 다른 글

'Mathematics' Related Articles

티스토리툴바