| [ QuizWit ] in KIDS 글 쓴 이(By): skykim (스카이킴) 날 짜 (Date): 2006년 1월 16일 월요일 오후 01시 30분 55초 제 목(Title): Re: 소수 구글로 찾아보니 증명 과정이 있는데 맞는 건지는 모르겠습니다. 수학엔 젬병이라 원문은 http://www.math.niu.edu/~rusin/known-math/99/bonse 에 있습니다. ----전 략-------- First, let k be a positive integer and consider the set { p_1*p_2*...*p_{k-1}*i - 1 | 1 <= i <= p_k }; no element of this set is divisible by any of the first k-1 primes and, if p >= p_k is any other prime, p can divide *at*most*one* element of this set. (If it divides 2 different elements, then it divides their difference which is of the form p_1*p_2*...*p_{k-1}*j with j < p_k -- impossible.) A peculiar consequence of this observation is that, if n - k + 1 < p_k,then there is some element of the set which is not divisible by any of the first n primes -- that's because each of the n - k + 1 primes p_k, ..., p_n can divide no more than one of the p_k elements of the set, so one version of the Pigeonhole Principle says that there's got to be some element left over. Such an element has its least prime divisor >= p_{n+1} and it is obviously <=p_1*p_2*....*p_k - 1 so we've proved: If n - k + 1 < p_k, then p_{n+1} < p_1*p_2*...*p_k. Now, fix n and let k be the *smallest* positive integer such that our condition n - k + 1 < p_k holds. Then, n - (k-1) + 1 >= p_{k-1} or, equivalently, n - k >= p_{k-1} - 2. If you compare the values k & p_{k-1} - 2 for increasing k, you'll see that p_{k-1} - 2 >= k for k >= 5. (Well, you'll certainly see that this is true for k = 5 -- but, once it's true for some value of k, it's clearly true for all larger values since the LHS increases by at least 2 at each step ...) Furthermore, if n >= 10 and k is chosen as above, then necessarily k >= 5. (Otherwise, n >= 10 and k <= 4 implies that n - k + 1 >= 10 - 4 + 1 = 7 = p_4, contradicting the choice of k.) So we've reached our next waystation: If n >= 10, then p_{n+1} < p_1*p_2*...*p_k for some k such that n - k >=k. But, then, using the obvious fact that p_i < p_{k+i} for i > 0, we get (p_{n+1})^2 < (p_1*p_2*...*p_k)*(p_1*p_2*...*p_k) < (p_1*p_2*...*p_k)*(p_{k+1}*p_{k+2}*...*p_{2k}) < p_1*p_2*...*p_{2k}*p_{2k+1}*...*p_n which is Bonse's inequality. This completes the proof under the assumption that n >= 10. By inspecting the situation for smaller values of n, we find that, in fact, the inequality holds for n >= 4 (as originally asserted). |