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$
  • 2
    $\begingroup$ "that there is always a prime number between $n$ and $2n$" The names Bertrand and Chebyshev spring to mind. $\endgroup$ – Daniel Fischer Jul 26 '13 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$ – dotslash Jul 26 '13 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$ – Daniel Fischer Jul 26 '13 at 14:35
  • $\begingroup$ Yes, I do. But not sure how to use it here. $\endgroup$ – dotslash Jul 26 '13 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$ – Daniel Fischer Jul 26 '13 at 14:40
14
$\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$
  • $\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$ – dotslash Jul 26 '13 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$ – 6005 Jul 26 '13 at 14:55
  • $\begingroup$ Precisely my thinking! Thank you for the concise and beautiful answer! $\endgroup$ – dotslash Jul 26 '13 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$
  • $\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$ – 6005 Jul 26 '13 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$ – 6005 Jul 26 '13 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 Jul 26 '13 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$
  • $\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$ – dotslash Jul 26 '13 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$ – Ross Millikan Jul 26 '13 at 15:10
  • $\begingroup$ I follow you now. Thanks for the answer! $\endgroup$ – dotslash Jul 26 '13 at 15:42

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.