# Prove n<prime<n!

1. Mar 11, 2009

### SneakyArab

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. Mar 11, 2009

### mblack

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.

3. Mar 11, 2009

### SneakyArab

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.

4. Mar 11, 2009

### mblack

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.

5. Mar 11, 2009

### SneakyArab

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.

6. Mar 11, 2009

### Dick

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?

7. Mar 11, 2009

### SneakyArab

I don't know :(
I feel stupid that I still don't know what that leads to.

8. Mar 11, 2009

### Dick

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
9. Mar 11, 2009

### SneakyArab

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

10. Mar 11, 2009

### Dick

You could clarify that a lot by putting in reasons for each step.

11. Mar 11, 2009

### SneakyArab

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