# Prime number

• Dec 3rd 2008, 06:28 AM
vincisonfire
Prime number
Prove that there is a prime number p such that n < p < n! for all n <2. n is an integer.
I'm not allowed to use Prime number theorem or this kind of stuff. Should be simple, but you must think of it!
• Dec 3rd 2008, 06:58 AM
PaulRS
Let $q_n$ be the greatest prime, less or equal than $n$, then $2^{q_n}-1$ can only be divisible by primes greater than $q_n$ ( see here), thus,let $p$ be a prime number satisfying $p|(2^{q_n}-1)$ then $p>n\geq{q_n}$ (1) ( since otherwise we'd contradict our definition of $q_n$)

From $n\geq{q_n}$ it follows that $n!>2^n-1 \geq 2^{q_n}-1$ if $n>3$ ( show by induction that $n!>2^n$ for all $n>3$ )

Thus, since $p|(2^{q_n}-1)$ we have $n!>2^{q_n}-1\geq{p}$ (2)

(1) and (2) complete the proof for $n>3$
• Dec 3rd 2008, 05:25 PM
JaneBennet
Quote:

Originally Posted by vincisonfire
Prove that there is a prime number p such that n < p < n! for all n > 2. n is an integer.

For $n=3$ we can take $p=5.$ Assume that $n>3.$

Suppose to the contrary there is no prime $p$ with $n

Let $p_1,\ldots,p_r$ be all the primes less than or equal to $n$ and consider $k=p_1\cdots p_r+1.$

$k$ is greater than 1 and not divisible by any of the primes $p_1,\ldots,p_r;$ hence $k$ must be divisible by a prime $q\notin\{p_1,\ldots,p_r\}.$

It follows that $n!\leqslant q\leqslant k=p_1\cdots p_r+1.$ But $p_1\cdots p_r\mid n!,$ say $n!=bp_1\cdots p_r.$

Hence $bp_1\cdots p_r\leqslant p_1\cdots p_r+1$ $\Rightarrow$ $(b-1)p_1\cdots p_r\leqslant1.$ This can only hold if the LHS is 0, i.e. $b=1$ $\Rightarrow$ $n!=p_1\cdots p_r.$ This is impossible for $n\geqslant4$ (contradiction).
• Dec 3rd 2008, 05:40 PM
ThePerfectHacker
Quote:

Originally Posted by JaneBennet
For $n=3$ we can take $p=5.$ Assume that $n>3.$

Suppose to the contrary there is no prime $p$ with $n

Let $p_1,\ldots,p_r$ be all the primes less than or equal to $n$ and consider $k=p_1\cdots p_r+1.$

$k$ is greater than 1 and not divisible by any of the primes $p_1,\ldots,p_r;$ hence $k$ must be divisible by a prime $q\notin\{p_1,\ldots,p_r\}.$

It follows that $n!\leqslant q\leqslant k=p_1\cdots p_r+1.$ But $p_1\cdots p_r\mid n!,$ say $n!=bp_1\cdots p_r.$

Hence $bp_1\cdots p_r\leqslant p_1\cdots p_r+1$ $\Rightarrow$ $(b-1)p_1\cdots p_r\leqslant1.$ This can only hold if the LHS is 0, i.e. $b=1$ $\Rightarrow$ $n!=p_1\cdots p_r.$ This is impossible for $n\geqslant4$ (contradiction).

I think you might make your proof a little simple though not necessary.
Let $p_1,...,p_r$ be the primes less than or equal to $n$.
Define $k=p_1\cdot ... \cdot p_r + 1$ and we see there is a prime divisor $q \not \in \{ p_1,...,p_r \}$.
Then, $n < q \leq k < n!$.