Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/