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$ 24 Answers
$\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$ 2 $\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$ 2 $\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$ 0 $\begingroup$If n = 3 then 3 < 5 < 6 = 3! If n = 4 then 4 < 7 < 24 = 4! If n > 4, let ∏p¡(n) be the product of the first k primes such that p¡ < n. For example, if n = 12, then ∏p¡(n) = 235711. Clearly, ∏p¡(n) divides n! because every factor of ∏p¡(n) is a factor of n!. So ∃ k ∈ N, k > 1 such that k∏p¡(n) = n!. Since k > 1 and ∏p¡(n) > 1, (k - 1)∏p¡(n) > 1. So, n! = (k - 1 + 1)∏p¡(n) = (k - 1)∏p¡(n) + ∏p¡(n) > 1 + ∏p¡(n). If n is prime then n divides ∏p¡(n), so that n < ∏p¡(n) < ∏p¡(n) + 1 < n! If n is composite, then n divides (n-1)! As before, for n-1, ∃ k ∈ N such that k∏p¡(n-1) = (n-1)! Since ∏p¡(n-1) > 1 and n divides (n-1)! we have that (n-1)!/k = nd, for some positive integer d. Therefore, ∏p¡(n-1) > n. Since ∏p¡(n) ≥ ∏p¡(n-1), we have that ∏p¡(n) + 1 > ∏p¡(n) ≥ ∏p¡(n-1) > n. By Euclid's Theorem, ∏p¡(n) + 1 is prime. Therefore, we have shown there exists at least one prime number between n and n! for all n ∈ N, n > 2.
Reference:
$\endgroup$
