I need some help with a proof. I just need to be pointed in the right direction, because I've been looking at this for ages and it's not clicking.
I need to prove that there are infinitely many prime numbers, by contradiction. The original statement is:
For all $n$ in $\mathbb{N}$ where $n > 2$, there exists a $p$ in $\mathbb{P}$[prime] such that $n < p < n!$.
We were given the hint that we're supposed to use cases to solve this. Case one is that $n!-1$ is prime, whereby obviously the statement holds.
case two is that $n!-1$ is composite, which is somehow also supposed to prove the statement, and I don't understand how. I know that every natural number $> 1$ has at least one prime factor, but I don't understand how we know that that prime factor is greater than n.
I also don't really understand how to do these cases using contradiction. Maybe I wrote the contradiction wrong, but I thought it came out to :
For all $p$ in $P$, there exists an $n$ in $\mathbb{N}$ where $n > 2 $, such that $n \le p \le n!$.
But maybe I did that wrong?
Can anyone give me a pointer on how to tie this together or where to start? I'd really appreciate it, thank you.
Best Answer
Case 1, as you already said, is trivial.
Case 2 is a little more tricky. Suppose that n!-1 is composite. Then it must be divisible by at least two primes, as you have already stated. But since n! is divisible by all numbers less than n, consider- what numbers less than n could go into n!-1?