Proof of Prime Divisor Existence for n>2

[SneakyArab]

Homework Statement

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.)

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.

 

[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.

 

[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.

 

[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.

 

[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.

 

[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?

 

[SneakyArab]

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

 

[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!.

 

[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

 

[Dick]

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

 

[SneakyArab]

right, I had a couple of laws floating around in my head that I just didnt put.

Thank you so much.