5
$\begingroup$

I need to prove that:

$$(1) \ \forall n\in\Bbb{N}_{\ge2}, \ \exists p\in \Bbb{P} : n < p < n!$$

I already know how to prove the $n < p$ part; it directly follows from the proof that there is no largest prime. However, I am stumped on the $p < n!$ part.

One idea I had for showing this is as follows: we know that $(2) \ \forall n \in \Bbb{N}_{\ge2},\ \exists m\in\Bbb{N} : n!=2m$. By testing a few values, I conjectured that $(3) \ \forall n\in\Bbb{N}_{\ge2}, \ \exists p\in \Bbb{P} : n < p < 2n$. If (3) could be shown, it would be simple to prove (1), but there does not seem to be no easy way to prove (3), if it's even correct.

$\endgroup$
5
  • 2
    $\begingroup$ "that there is always a prime number between $n$ and $2n$" The names Bertrand and Chebyshev spring to mind. $\endgroup$ Commented Jul 26, 2013 at 14:32
  • $\begingroup$ Oh, wow! I didn't know that! I was just trying to find a 'lazy' solution. But it's nice to know. :) $\endgroup$
    – ankush981
    Commented Jul 26, 2013 at 14:33
  • 2
    $\begingroup$ There's also an easy direct way. Do you know Euclid's proof that there are infinitely many primes? $\endgroup$ Commented Jul 26, 2013 at 14:35
  • $\begingroup$ Yes, I do. But not sure how to use it here. $\endgroup$
    – ankush981
    Commented Jul 26, 2013 at 14:36
  • $\begingroup$ I was thinking of what Goos answered. That relieves of the burden of proving that the product of primes $< n$ is $> n$ (although that's not very hard). $\endgroup$ Commented Jul 26, 2013 at 14:40

3 Answers 3

15
$\begingroup$

Just consider $n! - 1$. Clearly this is between $n$ and $n!$ as long as there is anything between $n$ and $n!$, and it isn't divisible by any prime $p \le n$. Thus it contains a prime factor bigger than $n$ and smaller than $n!$.

$\endgroup$
3
  • $\begingroup$ Correct me if I'm wrong, but $n! -1$ isn't divisible by any prime less than $n$ because all the primes are already included in $n!$ ? $\endgroup$
    – ankush981
    Commented Jul 26, 2013 at 14:53
  • $\begingroup$ @dotslash For any prime $p \le n$, $p$ is contained in the product $n!$, so $n! - 1$ is one less than a multiple of $p$. $\endgroup$ Commented Jul 26, 2013 at 14:55
  • $\begingroup$ Precisely my thinking! Thank you for the concise and beautiful answer! $\endgroup$
    – ankush981
    Commented Jul 26, 2013 at 14:59
3
$\begingroup$

You can obviously proceed by stating the Bertrand's postulate. However, I think the question is asking you to solve it a bit differently.

Let us solve it using a method similar to that used by Euclid when he tried to prove that there are infinite number of primes. Let $p_{1},p_{2},\cdots ,p_{k}$ be all the primes less than or equal to $n$. Obviously, $k<n$.Let, $P=p_{1}\times p_{2}\times\cdots \times p_{k}+1$.

Notice that $P$ is not divisible by any of the given primes. Hence $P$ is either a prime or is divisible by a prime $> n$.

It can be easily seen that $$P<n!$$ Furthermore, $P$ needs to be greater than $n$, otherwise we would find another prime (other than $p_{1},p_{2},\cdots,p_{k}$) which would lead to a contradiction.

$\endgroup$
3
  • $\begingroup$ I think you mean that $p_1, p_2, \cdots , p_k$ are less than or equal to $n$. You also have to be careful when claiming that $P < n!$; this isn't true in the case $n = 3$. $\endgroup$ Commented Jul 26, 2013 at 14:42
  • $\begingroup$ You need it to not be divisible by $n$ if $n$ is prime, so you need to include primes less than or equal to $n$ in the product. Thus you get $3*2 + 1 = 7$, not less than $3! = 6$. $\endgroup$ Commented Jul 26, 2013 at 14:47
  • $\begingroup$ Sorry!My bad,I guess the case n=3 has to be checked manually.Other than that I think there are no exceptions. $\endgroup$
    – Shaswata
    Commented Jul 26, 2013 at 14:49
2
$\begingroup$

What you speculate on is correct, there is always a prime between $n$ and $2n$. This is known as Bertrand's postulate and is really a theorem. But for between $n$ and $n!$ you can modify the Euclid proof for a much easier approach. It is true for $3, 3 \lt 5 \lt 6$. For $n \gt 3,$ take the product of all primes less than $n$ and add $1$. This is less than $n!$ because it has only one factor of $2$, not the three coming from $2$ and $4$. Then it is either prime or composite ...

$\endgroup$
3
  • $\begingroup$ Great! But your explanation of "only one factor of $2$" confuses me. Isn't it simpler to say that $n!$ contains all the integers between $2$ and $n$, including those that are prime. Hence, $n! > p$? $\endgroup$
    – ankush981
    Commented Jul 26, 2013 at 14:46
  • $\begingroup$ But we need a prime greater than $n$ and $n!$ doesn't contain that as a factor. I wanted to justify that the product of all the primes less than $n$ is strictly less than $n!$ so that I could add one and still be less. Identifying a factor of $n!$ that is not part of the product of primes was my way of doing that. That is also why I did $3$ separately-it is not true in that case as you can see. If we just take all the primes less than or equal to $3$, the product plus $1$ is $7$ and we have not found a prime between $3$ and $3!$ $\endgroup$ Commented Jul 26, 2013 at 15:10
  • $\begingroup$ I follow you now. Thanks for the answer! $\endgroup$
    – ankush981
    Commented Jul 26, 2013 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .