Is There Always a Prime Number Between n and n! for n>2?

[theIBnerd]

Hello. I have to prove the fallowing theorem:

"There is at least one prime number between n and n! (n factorial) for all n>2."

I would be happy if you could prove this theorem for me or at least tell me if you have used the rule of Infinity of Prime Numbers in your proof. Thank you.

 

[LeonhardEuler]

We can't do this for you, but we can help you. If you look through the usual proof that there are infinitely many primes (Euclid's proof), you might see that you can modify it slightly to prove this result.

 

[pzona]

I'm not sure on this, but perhaps you can use the fact that there is always a prime between n and 2n. A factorial for a number x greater than 2 will always be some number less than x, times x, and since x>2, the first rule I stated applies.

 

[OwlHoot]

Hello. I have to prove the fallowing theorem:

"There is at least one prime number between n and n! (n factorial) for all n>2."

I would be happy if you could prove this theorem for me or at least tell me if you have used the rule of Infinity of Prime Numbers in your proof. Thank you.

Use the Chinese Remainder Theorem to find an integer == 1 mod each prime < n and hence an integer == 1 mod (n-1)!.

Then adding to the latter integer a suitable multiple of (n-1)! yields an integer with the same property in the range [n, n!] (whose width is > (n-1)!), and every prime factor of this integer must be in the same range.

This doesn't rely on the fact that there are an infinite number of primes (and therefore proves this).

 

[theIBnerd]

I'm not sure on this, but perhaps you can use the fact that there is always a prime between n and 2n. A factorial for a number x greater than 2 will always be some number less than x, times x, and since x>2, the first rule I stated applies.

Yes I have thought of Bertrand's Postulate, too; but I need a distinct proof of the theorem. Thank you anyway.

We can't do this for you, but we can help you. If you look through the usual proof that there are infinitely many primes (Euclid's proof), you might see that you can modify it slightly to prove this result.

Use the Chinese Remainder Theorem to find an integer == 1 mod each prime < n and hence an integer == 1 mod (n-1)!.

Then adding to the latter integer a suitable multiple of (n-1)! yields an integer with the same property in the range [n, n!] (whose width is > (n-1)!), and every prime factor of this integer must be in the same range.

This doesn't rely on the fact that there are an infinite number of primes (and therefore proves this).

OwlHoot, thank you for extending LeonhardEuler's answer and proving the theorem. Your proof to the theorem seems elegant.

I also reached another proof of the theorem, which goes:

If n = 3 then 3 < 5 < 6 = 3!
If n = 4 then 4 < 7 < 24 = 4!

If n > 4, let ∏p¡(n) be the product of the first k primes such that p¡ < n. For example, if n = 12, then ∏p¡(n) = 2*3*5*7*11. Clearly, ∏p¡(n) divides n! because every factor of ∏p¡(n) is a factor of n!. So ∃ k ∈ N, k > 1 such that k∏p¡(n) = n!. Since k > 1 and ∏p¡(n) > 1, (k - 1)∏p¡(n) > 1. So, n! = (k - 1 + 1)∏p¡(n) = (k - 1)∏p¡(n) + ∏p¡(n) > 1 + ∏p¡(n).

If n is prime then n divides ∏p¡(n), so that n < ∏p¡(n) < ∏p¡(n) + 1 < n!

If n is composite, then n divides (n-1)! As before, for n-1, ∃ k ∈ N such that k∏p¡(n-1) = (n-1)! Since ∏p¡(n-1) > 1 and n divides (n-1)! we have that (n-1)!/k = nd, for some positive integer d. Therefore, ∏p¡(n-1) > n. Since ∏p¡(n) ≥ ∏p¡(n-1), we have that ∏p¡(n) + 1 > ∏p¡(n) ≥ ∏p¡(n-1) > n.

By Euclid's Theorem, ∏p¡(n) + 1 is prime. Therefore, we have shown there exists at least one prime number between n and n! for all n ∈ N, n > 2.

 

[srijithju]

Use the Chinese Remainder Theorem to find an integer == 1 mod each prime < n and hence an integer == 1 mod (n-1)!.

Then adding to the latter integer a suitable multiple of (n-1)! yields an integer with the same property in the range [n, n!] (whose width is > (n-1)!), and every prime factor of this integer must be in the same range.

This doesn't rely on the fact that there are an infinite number of primes (and therefore proves this).

OwlHoot,

A few questions here , how is it that if an integer == 1 mod each prime < n then that integer == 1 mod (n-1)! ??

eg. consider n = 6 ,
then the required integer = 2*3*5 + 1 ( becoz it gives rem 1 with all primes < 6)

but 2*3*5 + 1 mod (6-1)! , ie mod 120 is certainly not == 1 .

it is rather == 31

Now if u wanted a no that is == 1 mod (n-1)! , and hence == 1 mod any prime < n ,
u would be looking for x.(n-1)! + 1 where x is any integer .

Now again considering n= 6 , this means the integer we are lookin for is x.(6-1)! +1 i.e.

120x + 1
Now the suitable value of x such that
n < 120x + 1 < n!
is x= 1
hence the number we are supposed to be looking at is 121
but 121 = 11^2 , hence is not a prime number. So the proof is wrong.

Or have I got something seriously wrong over here ??

 

[srijithju]

Yes I have thought of Bertrand's Postulate, too; but I need a distinct proof of the theorem. Thank you anyway.OwlHoot, thank you for extending LeonhardEuler's answer and proving the theorem. Your proof to the theorem seems elegant.

I also reached another proof of the theorem, which goes:

If n = 3 then 3 < 5 < 6 = 3!
If n = 4 then 4 < 7 < 24 = 4!

If n > 4, let ∏p¡(n) be the product of the first k primes such that p¡ < n. For example, if n = 12, then ∏p¡(n) = 2*3*5*7*11. Clearly, ∏p¡(n) divides n! because every factor of ∏p¡(n) is a factor of n!. So ∃ k ∈ N, k > 1 such that k∏p¡(n) = n!. Since k > 1 and ∏p¡(n) > 1, (k - 1)∏p¡(n) > 1. So, n! = (k - 1 + 1)∏p¡(n) = (k - 1)∏p¡(n) + ∏p¡(n) > 1 + ∏p¡(n).

If n is prime then n divides ∏p¡(n), so that n < ∏p¡(n) < ∏p¡(n) + 1 < n!

If n is composite, then n divides (n-1)! As before, for n-1, ∃ k ∈ N such that k∏p¡(n-1) = (n-1)! Since ∏p¡(n-1) > 1 and n divides (n-1)! we have that (n-1)!/k = nd, for some positive integer d. Therefore, ∏p¡(n-1) > n. Since ∏p¡(n) ≥ ∏p¡(n-1), we have that ∏p¡(n) + 1 > ∏p¡(n) ≥ ∏p¡(n-1) > n.

By Euclid's Theorem, ∏p¡(n) + 1 is prime. Therefore, we have shown there exists at least one prime number between n and n! for all n ∈ N, n > 2.

I didnt understand the proof completely , but this is what I think u meant :

you have proved that ∏p¡(n) + 1 + 1 > n and < n!, and then concluded that ∏p¡(n) + 1 is a prime number due to some theorem by euclid.

Well if that's the case , then what I can say is ∏p¡(n) + 1 , need not be a prime number at all :
All euclids theorem states is that either ∏p¡(n) + 1 is prime OR there exists some other prime number (say M) greater than [p][/i] where [p][/i] is the largest prime < n , such that M divides ∏p¡(n) + 1 exactly.
Anyhow this does prove your theorem , because M > n and M <= ∏p¡(n) + 1 < n!

Sorry for the formatting .. I really donno how to use this latex formatting thing

 

[LeonhardEuler]

If n is composite, then n divides (n-1)! As before, for n-1, ∃ k ∈ N such that k∏p¡(n-1) = (n-1)! Since ∏p¡(n-1) > 1 and n divides (n-1)! we have that (n-1)!/k = nd, for some positive integer d. Therefore, ∏p¡(n-1) > n. Since ∏p¡(n) ≥ ∏p¡(n-1), we have that ∏p¡(n) + 1 > ∏p¡(n) ≥ ∏p¡(n-1) > n.

The logic here is a little unclear to me.

By Euclid's Theorem, ∏p¡(n) + 1 is prime. Therefore, we have shown there exists at least one prime number between n and n! for all n ∈ N, n > 2.

Euclid's proof does not show that ∏p¡(n) + 1 is prime. It shows that there is some prime number between n and ∏p¡(n) + 1 (a prime number p such that $$n < p \leq \Pi\pi(n)+1$$ to be exact). (for instance 2*3*5*7*11*13+1=30031= 59*509)This would still be enough to prove the theorem assuming all the previous steps are correct.

The way I was thinking of proving it was simpler, a proof by contradiction:

Let x be a number such that there is no prime between x and x! and x>2. Form the product of all primes less than or equal to x, and add 1 to this. Call this number y.

For x>3, y is less than x!: $$y=\Pi\pi(n) + 1< 4*\Pi\pi(n) \leq x!$$. The first step works because the product of primes is greater than 1. The second step works because 4 is composite, so it will be present in x!, but not in the product of primes for x>3. The theorem is obvious for x=3, so x cannot be 3.

y cannot be prime, because y<x! and there are no primes between x and x!

y cannot be composite: No prime number less than or equal to x divides y because all such prime numbers divide the product of primes less than or equal to x, so are of the form n+1/q for integers n and q>1. No primes greater than x! divide y because y<x!. There are no primes between x and x!.

But y must be prime or composite. Contradiction.

 

[srijithju]

The logic here is a little unclear to me.



Euclid's proof does not show that ∏p¡(n) + 1 is prime. It shows that there is some prime number between n and ∏p¡(n) + 1 (a prime number p such that $$n < p \leq \Pi\pi(n)+1$$ to be exact). (for instance 2*3*5*7*11*13+1=30031= 59*509)This would still be enough to prove the theorem assuming all the previous steps are correct.

The way I was thinking of proving it was simpler, a proof by contradiction:

Let x be a number such that there is no prime between x and x! and x>2. Form the product of all primes less than or equal to x, and add 1 to this. Call this number y.

For x>3, y is less than x!: $$y=\Pi\pi(n) + 1< 4*\Pi\pi(n) \leq x!$$. The first step works because the product of primes is greater than 1. The second step works because 4 is composite, so it will be present in x!, but not in the product of primes for x>3. The theorem is obvious for x=3, so x cannot be 3.

y cannot be prime, because y<x! and there are no primes between x and x!

y cannot be composite: No prime number less than or equal to x divides y because all such prime numbers divide the product of primes less than or equal to x, so are of the form n+1/q for integers n and q>1. No primes greater than x! divide y because y<x!. There are no primes between x and x!.

But y must be prime or composite. Contradiction.

Well .. I think u got it absolutely right here ... I was saying the same thing basically .. that x < \Pi\pi(n) +1 < x! ... but nice to see your proof of it ...
by the way thanks for ur example (for instance 2*3*5*7*11*13+1=30031= 59*509) ... coz i was searching for such an example but couldn't find one