14
$\begingroup$

How to prove that there exists a prime number between $n$ and $ n!$, for all $ n> 2$?


(Bertrand's postulate gives a much better bound, but this question is about obtaining a self-contained proof.)

$\endgroup$
  • 2
    $\begingroup$ Since this is a site that encourages learning, you will get much more help if you show us what you have already done. Could you edit your question with your thoughts and ideas? $\endgroup$ – 5xum Dec 29 '14 at 7:31
  • $\begingroup$ For $n\geq 3$, take $p$ as a prime divisor of $n!-1$. $\endgroup$ – Kelenner Dec 29 '14 at 8:02
16
$\begingroup$

Given $n>2$. So for every integer $x$ such that $1<x<(n+1),$ we have $x|n!$ and $x\not|(n!-1).$

$\therefore$ either $(n!-1)$ is a prime, or $\exists$ a prime $p\ge (n+1) $ such that $p|(n!-1)$.

So in any case, $\exists$ a prime $p$ such that $(n+1)\le p\le (n!-1)$.

$\endgroup$
6
$\begingroup$

For $n=2$ take $p=2$. For $n\geq 3$, take $p$ as a prime divisor of $n!-1$ (hence $p<n!$). Then $p>n$, if not, $p$ divide $n!$, hence divide $n!-(n!-1)=1$.

$\endgroup$
  • $\begingroup$ Why does p divide $ n! - (n!-1) $? $\endgroup$ – LanceHAOH Sep 17 '16 at 8:49
3
$\begingroup$

Base case: $3<5<3!$

Induction Hypothesis: Suppose that $\exists p$ such that $p$ is prime and $(n-1)<p<(n-1)!$

Induction Step: We must now show that $\exists k$ such that $k$ is prime and $n<k<n!$.

So either $n=p$ or $n<p<(n-1)!<n!$ If the case is the latter one, we are done. So, suppose that $n=p$. Now, we consider $Q=\prod p_i$ where $p_i\leq p$ and $p_i$ is prime. Well, we actually consider $Q+1$. Notice that $p<Q+1<n!$ Furthermore, notice that no primes less than or equal to $p$ divide $Q+1$ (because of the left over 1). Hence, either $Q+1$ is prime or composite. If $Q+1$ is prime, we are done. If $Q+1$ is composite (and since no prime less than or equal to $p$ divides $Q+1$) there must exist some $q<t<Q+1<n!$ such that $t|(Q+1)$. Thus, we are finished by setting $k=Q+1$ or $k=t$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.