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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum