Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof that exists prime btw n<p<n!

  1. Oct 11, 2012 #1
    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+∏pi (where pi is the ith prime less ≤n) is a prime and ∏pi | ∏ni=n! and since 4 is a factor of n! but not ∏pi, ∏pi | 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.
     
  2. jcsd
  3. Oct 11, 2012 #2
    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?
     
  4. Oct 12, 2012 #3
    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.
     
  5. Oct 12, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Can't one of the pi be a factor of n+1?
     
  6. Oct 12, 2012 #5
    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.
     
  7. Oct 12, 2012 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  8. Oct 12, 2012 #7
    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.
     
  9. Oct 12, 2012 #8
    How do we know Q < n! ?
     
  10. Oct 13, 2012 #9
    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!
     
    Last edited: Oct 13, 2012
  11. Oct 19, 2012 #10
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook