Prime Numbers between N and 1+N!Date: 04/25/2003 at 23:46:31 From: John Subject: Prime numbers between n and 1 + N! I've been trying to find a proof of the fact that for each natural number N, there exists a prime number Q such that N is less than or equal to Q and Q is less than or equal to 1 + N! Date: 04/26/2003 at 09:31:21 From: Doctor Paul Subject: Re: Prime numbers between n and 1 + N! Let f(x) = 2*x and g(x) = x! + 1 and let N = 1. f(N) = 2 g(N) = 2 So Q = 2 is the only choice. Now let N = 2. Then f(N) = 4 and g(N) = 3. Clearly, there is no prime Q such that 4 <= Q <= 3. So the condition isn't true for N = 2. Now let N = 3. Then f(N) = 6 and g(N) = 7 and we have Q = 7. If N = 4, we have f(N) = 8, g(N) = 25, and we have many choices for Q. The key to this problem is to show that for N >= 3 we have f(N) < g (N). Then we can apply Bertrand's Postulate, which guarantees the existence of a prime between n and 2*n for all natural numbers n > 1. There is more about that in Eric Weisstein's World of Mathematics: Bertrand's Postulate http://mathworld.wolfram.com/BertrandsPostulate.html To prove that 2*n < n! + 1 for n >=3, use induction. It is easily shown to be true for n = 3 since 6 < 7. Now suppose that 2*n < n! + 1 and consider 2*(n+1) = 2*n + 2 < n! + 3 < n! + 1 < n!*(n+1) +1 = (n+1)! + 1. Thus we have 2*(n+1) < (n+1)! + 1 and so by the principle of mathematical induction, we know that 2*n < n! + 1 for n >=3. Now apply Bertrand's Postulate and you're finished. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 03/10/2012 at 05:06:35 From: Marius Subject: A better proof for an already solved problem! Hi, I don't want to ask a question. Rather, I want to provide a better proof for the fact "for all natural numbers N, there is a prime number in the interval (N, N! + 1]." The one above uses a very strong result, i.e., Bertrand's Postulate. This is likely not what most people are looking for. But since this proof is one of the first results if I Google for this problem, I think it is better to give another proof. Here is a simpler proof: Let N be a natural number. Assume that there is no prime number in (N, N! + 1]. Let b := 2*3*5*7*11*...*p Here, p is prime and p <= N (the product of all prime numbers less than or equal to N, also known as the primordial N#). Of course, b <= N! and this means b + 1 <= N! + 1. By our assumption, b + 1 cannot be a prime number. So there exists at least one prime number q which divides b + 1. This has to be smaller than b + 1 and this means it has to be one of the primes 2, 3, 5, 7, 11, ..., p (since there is no prime greater than p and smaller than b + 1, by assumption). This means that q divides not only b + 1 but also b (by definition of b). Then q must also divide the difference between b and b + 1, which is 1. But this cannot be the case, since q is a prime number. So the assumption was wrong, and we have proven that there has to be at least one prime number in (N, N! + 1]. Cheers, Marius |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/