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!

Printable View

- Dec 3rd 2008, 06:28 AMvincisonfirePrime 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 AMPaulRS
Let $\displaystyle q_n$ be the greatest prime, less or equal than $\displaystyle n$, then $\displaystyle 2^{q_n}-1$ can only be divisible by primes greater than $\displaystyle q_n$ ( see here), thus,let $\displaystyle p$ be a prime number satisfying $\displaystyle p|(2^{q_n}-1)$ then $\displaystyle p>n\geq{q_n}$ (1) ( since otherwise we'd contradict our definition of $\displaystyle q_n$)

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

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

(1) and (2) complete the proof for $\displaystyle n>3$ - Dec 3rd 2008, 05:25 PMJaneBennet
For $\displaystyle n=3$ we can take $\displaystyle p=5.$ Assume that $\displaystyle n>3.$

Suppose to the contrary there is no prime $\displaystyle p$ with $\displaystyle n<p<n!.$

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

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

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

Hence $\displaystyle bp_1\cdots p_r\leqslant p_1\cdots p_r+1$ $\displaystyle \Rightarrow$ $\displaystyle (b-1)p_1\cdots p_r\leqslant1.$ This can only hold if the LHS is 0, i.e. $\displaystyle b=1$ $\displaystyle \Rightarrow$ $\displaystyle n!=p_1\cdots p_r.$ This is impossible for $\displaystyle n\geqslant4$ (contradiction). - Dec 3rd 2008, 05:40 PMThePerfectHacker
I think you might make your proof a little simple though not necessary.

Let $\displaystyle p_1,...,p_r$ be the primes less than or equal to $\displaystyle n$.

Define $\displaystyle k=p_1\cdot ... \cdot p_r + 1$ and we see there is a prime divisor $\displaystyle q \not \in \{ p_1,...,p_r \}$.

Then, $\displaystyle n < q \leq k < n!$.