1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove n<prime<n!

  1. Mar 11, 2009 #1
    1. The problem statement, all variables and given/known data

    Given: For all n > 2, there exists a prime p : n < p < n!

    (given hint: Since n>2, one has n!-1>2 and therefore n!-1 has a prime divisor p.)


    3. The attempt at a solution

    I made an attempt at doing the proof by induction, as the previous question was by induction. However, I am not very good at induction at all. Here is what I have:

    Start: n=3 => 3< 5 < 6
    Hypothesis: Let P(n) be true for some n >= 3
    Step: Show P(n+1) true: n+1 < (n+1)! -1 < (n+1)!

    n+1 < n!*(n+1)-1 < n!*(n+1)
    ...
    and then I don't know where to go. I tried throwing around some numbers, but I don't understand what I'm supposed to be looking for really.
     
  2. jcsd
  3. Mar 11, 2009 #2
    I think it might help if you remember that n and n+1 are relatively prime. Think about what you can divide the equation you have in your step by to obtain such a situation.
     
  4. Mar 11, 2009 #3
    Sorry, I'm very new to discrete math and doing a lot of proofs, and I don't understand what you mean :(

    I'm a proof newbie, if you will.
     
  5. Mar 11, 2009 #4
    Well, I tried it using my original idea and I couldn't do it that way anyway. However, relatively prime means that if two numbers are separated by an integer (example: 9,10), there is no number that divides both of them evenly except for 1 of course. Thus, any combo of n and n+1 are relatively prime. I'm working on another solution and I'll let you know if I get anything.
     
  6. Mar 11, 2009 #5
    Thanks. It doesn't have to be done by induction by the way, its just that that is one of the only proof methods that I have been taught thus far, and seemed like the most likely.
     
  7. Mar 11, 2009 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, you know n! is divisible by ALL primes p<=n, right? As mblack suggested, maybe looking at the wrong numbers, but well motivated, n! and n!-1 are relatively prime. That means there is a prime divisor of n!-1 that does NOT divide n!. Hence?
     
  8. Mar 11, 2009 #7
    I don't know :(
    I feel stupid that I still don't know what that leads to.
     
  9. Mar 11, 2009 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm just going to write the same words in a different order. So pay attention. n! is divisible by ALL primes less than or equal to n. Agreed? Or not? Your choice. If you have a question say why! If n!-1 has a prime divisor that is different from all of those numbers, then that prime divisor must be greater than n. You can feel stupid if you need to, but tell me where you disagree with this? It leads to the conclusion that there is a prime between n and n!.
     
    Last edited: Mar 11, 2009
  10. Mar 11, 2009 #9
    Ok I think I see now. So do I not need to do induction at all?
    Can I write the proof like this:

    For all n>2: there exists p prime: n<p<n!
    Proof:
    For all p<n: p | n! //p divides n!
    n! and n!-1 are relatively prime => n! and n!-1 share no common divisors
    => there must a prime p > n : p | n!-1
     
  11. Mar 11, 2009 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You could clarify that a lot by putting in reasons for each step.
     
  12. Mar 11, 2009 #11
    right, I had a couple of laws floating around in my head that I just didnt put.

    Thank you so much.
     
    Last edited: Mar 11, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook