proof that exists prime btw n<p<n!

Arijun

I'm trying to prove that for n>2, member of Z, exists some prime p s.t. n<p<n!. I have successfully proved it by saying there's no prime btw n and (n-1)!, but I want to prove it with my original thought:

first prove for 3, then for n>3:
p=1+∏p_i (where p_i is the ith prime less ≤n) is a prime and ∏p_i | ∏n_i=n! and since 4 is a factor of n! but not ∏p_i, ∏p_i | n!/4. from there you can prove p<n!

proving p>n is trickier. its easy when n factors into primes with each showing up not more than once, but I'm stuck on how to get it if n is, say, the square of two primes.

I'm pretty sure p is always > n because I tried it with the first ten thousand primes with no problems.

Robert1986

What about trying what you have, except do [itex]p=1+n+\Pi p_i[/itex]? This is always less than [itex]\leq 2n+1 \leq n![/itex] (when n is at least 4). Now, this doesn't have to be a prime BUT if there is some prime divisor, then it has to be between n an n+p+1, right? So, either p is prime and it is between n and n! OR it isn't prime which forces a prime between n and n+p+1, so either way, (when n is at least 4) there is a prime between n and n!.

BTW, why do you say there is no prime between n and (n-1)!? If n=4, (n-1)! = 3! = 6 and 4 is between 3 and 6. I'm guessing you made a typo?

Arijun

Why does there need to be a prime btw n and n+p+1?

I'm a little removed from my other proof at this point so I'm not entirely sure what I meant.

haruspex

Can't one of the p_i be a factor of n+1?

Robert1986

Yeah, for some reason I thought that each pi divided n, but that's not the case. Ok, so if we can use Bertrand's postulate, this is easy. But I'm trying to think of another way.

haruspex

Let P be the product of primes <= n. So P+1 is prime to all numbers <= n. If P < n, n must have repeated prime factors. We can multiply up P by such additional factors, never exceeding the number that occur in n, until we get Q > n. Still Q < n!, and Q+1 is prime to all numbers <= n (so is also < n!). If Q not prime it has a prime factor > n.

Robert1986

OK, just multiply p by 2 until it gets bigger than n. Then you can use what I said (that p is prime or there is a prime factor bigger than n.) And of course this is less than n! when n is bigger than 3.

EDIT: OK, I feel like an idiot, apparantley this issue was setteled already.

Arijun

How do we know Q < n! ?

ramsey2879

Because Q is merely a product of primes less or equal to n so multiples of primes such as 4 and 9 are not multiplied as they are for n!. Since there are less factors, the product is smaller. Even so Q+1 is not divisible by any prime less than or equal to n, this either Q+1 is prime or it is a product of primes that occur between n and n!

Boorglar

I think that it suffices to consider the number n! - 1.

clearly n < n! - 1 < n! for n > 2.

If n! - 1 is prime, the theorem is proven.
If n! - 1 is not prime, then it must be divisible by some prime number less than n! - 1 (and therefore less than n!). But it cannot be divisible by any number less than or equal to n (other than 1) since n! is divisible by 1,2,3,...,n. Therefore this prime number is greater than n. Choose p as this prime number. Then n < p < n! and p is prime, which proves the theorem.