Prime number

**vincisonfire** · December 3rd 2008, 06:28 AM

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!

**PaulRS** · December 3rd 2008, 06:58 AM

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$

**JaneBennet** · December 3rd 2008, 05:25 PM

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

**ThePerfectHacker** · December 3rd 2008, 05:40 PM

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<p<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!$ .

Thread: Prime number

LinkBack

Thread Tools

Display

Prime number

Similar Math Help Forum Discussions

Prove that if x^n - 3^n = a prime number, then x = 4 and n = a prime number

Prime number 2

Prime number

how to determine if a number is prime number??

Number theory, prime number

Search Tags