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

  • 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

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

  • $\begingroup$ And what if $n!-1$ is a prime. This is possible for $n=3, 4$. Just a few small examples. Could you please explain? $\endgroup$
    – Paul
    Feb 6 at 16:24
  • $\begingroup$ @Paul For any $n>2$ if $n!-1$ is a prime, then you can stop the search for existence of a prime between $n$ and $n!$. Try writing the usual ordering of the numbers being discussed here. $\endgroup$
    – Praveen
    Feb 6 at 16:51

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

  • $\begingroup$ Why does p divide $ n! - (n!-1) $? $\endgroup$
    – Donald
    Sep 17 '16 at 8:49
  • $\begingroup$ @Donald because if $p$ divides $n!-1$, and $p$ divides $n!$, then $p$ must divide their difference, namely, $p$ divides $n!-(n!-1)$. $\endgroup$
    – Prism
    Aug 3 '20 at 23:56

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


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.