8

I am trying to prove that ($\forall \ n\in\mathbb{N}$) there exists a prime number $q$ such that $n < q \le 1 + n!$

I have made a graph with $n=0$ through $n=10$ and found solutions to all of them looking for a pattern and I see that $n!$ gets enormous fast and it becomes quite obvious that there is a prime number in between them.

I have considered trying to prove by contradiction that $q$ does not exist on that interval, but I don't know where to go from that statement. Could anybody help me figure it out? I have been staring at it for hours and I can't figure out where to go.

Thank you.

Link

Glorfindel
  • 3,955
Sam
  • 419

6 Answers6

43

Hint: $n!+1$ has some prime factor $p$. If $p \leq n$ then $p\mid n!$.

Yuval Filmus
  • 57,157
  • wow.. nice answer +1. Your answe is better than my one. – Bumblebee Sep 26 '14 at 04:25
  • I am looking at this, and I do not know what math to use. I cannot figure out what the first step would be, do I use a contradiction? then what do I do after I am stating a contradiction?

    Is it that since n! and 1+n! are not divisible then there must be a prime number p that is greater than n that is a factor of n!+1?

    I'm sorry I did not mean to enter the comment before I said that

     – Sam Sep 26 '14 at 04:36
  • 5
    @Sam You'll have to figure this out yourself. – Yuval Filmus Sep 26 '14 at 04:38
  • I'm not clear about something, maybe it's just me. The requirement was that we find a prime $p \ni \exists n \in \mathbb{Z^+}, n < p < n! + 1$. However, then we may not take $p \leq n.$ – ThisIsNotAnId Sep 26 '14 at 04:44
  • 2
    @ThisIsNotAnId You too will have to figure this out yourself. – Yuval Filmus Sep 26 '14 at 04:45
  • @ThisIsNotAnId What does "$p \ni \exists n \in \mathbb{Z}^+$" mean? And the requirement was $n<p\leq n!+1$, not $n<p<n!+1$. – JiK Sep 26 '14 at 10:03
  • OK, to clarify - if $n!+1$ is prime, then we are done. If not, then suppose $q$ is one of its factors. $q<n!+1$ obviously. Now if $q<=n$, then both $q|n!+1$ (assumption above) and $q|n!$ (definition of $n!$). But this is not possible, therefore $q>n$. – Julia Hayward Sep 26 '14 at 13:35
  • @JuliaHayward Right, that's the idea. You don't even need to single out the case that $n!+1$ is prime, since even prime numbers have a prime factor. – Yuval Filmus Sep 26 '14 at 13:36
  • @JiK Thanks for pointing that out. The statement "$p \ni \exists n \in \mathbb{Z^+}$" means $p$ such that for some $n$ in $\mathbb{Z^+}$. – ThisIsNotAnId Sep 26 '14 at 17:16
  • @ThisIsNotAnId: then what you wrote was not at all the requirement. The statement to prove is $\forall n \exists$ prime $p : n < p \leq n! + 1$. (: is more common for "such that." $\ni$ means "contains the element.") – Nick Matteo Sep 26 '14 at 20:04
  • @Kundor It seems I wasn't paying much attention when I wrote that down, but the main point still remains. We may not pick $p \leq n$. Though, Yuval had in mind that we show $p > n$ by contradiction. – ThisIsNotAnId Sep 26 '14 at 21:31
13

HINT:
Use the Bertrand's postulate.
Since $n!\ge 2n$ for all $n\ge 3$ we have the result.

Bumblebee
  • 18,220
  • 5
  • 47
  • 87
6

All the primes dividing $n!$ give remainder $1$ when they divide $n!+1$. Those include all primes from $1$ to $n$. So either $n!+1$ is itself a prime, or it is divisible by a prime $>n$ and of course $\le n!+1$.

Iwillnotexist Idonotexist
  • 471
saikat1729
  • 111
4

For $n=1$ and $n=2$ the condition holds.

So to prove the statement assume $n>2$. Now 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)$.

$\therefore$ $\exists$ a prime number $p$ such that $n<p≤1+n!$ $\hspace{.2cm}$$,\forall n\in \mathbb{N}.$

Praveen
  • 1,613
4

$n!+1$ isn't divisible by the integers from $2$ to $n$. Then all its prime factors exceed $n$, and there is at least one.

3

Case 1) if n=1,2,3 then $q=2,3,7$

Case 2) for other n, $2n< n! $ Now we know $\exists q$ prime s.t $n<q<2n<1+n!$

Hence we are done.

Ri-Li
  • 9,038