7
$\begingroup$

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.

http://mathforum.org/library/drmath/view/62825.html

$\endgroup$
41
$\begingroup$

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

$\endgroup$
  • $\begingroup$ wow.. nice answer +1. Your answe is better than my one. $\endgroup$ – Bumblebee Sep 26 '14 at 4:25
  • $\begingroup$ 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 $\endgroup$ – Sam Sep 26 '14 at 4:36
  • 5
    $\begingroup$ @Sam You'll have to figure this out yourself. $\endgroup$ – Yuval Filmus Sep 26 '14 at 4:38
  • $\begingroup$ 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.$ $\endgroup$ – ThisIsNotAnId Sep 26 '14 at 4:44
  • 2
    $\begingroup$ @ThisIsNotAnId You too will have to figure this out yourself. $\endgroup$ – Yuval Filmus Sep 26 '14 at 4:45
13
$\begingroup$

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

$\endgroup$
  • 18
    $\begingroup$ This is overkill. $\endgroup$ – Yuval Filmus Sep 26 '14 at 4:21
  • 5
    $\begingroup$ If by "large $n$" you mean "$n > 3$", then, sure.. $\endgroup$ – Thomas Sep 26 '14 at 14:14
  • $\begingroup$ The OP was looking for a way to prove the statement from scratch, I guess. $\endgroup$ – Yves Daoust Nov 29 '16 at 18:52
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is precisely Nilan's answer. $\endgroup$ – daniel Sep 26 '14 at 4:32
  • $\begingroup$ Yeah I have just seen. $\endgroup$ – user152715 Sep 26 '14 at 4:32
3
$\begingroup$

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

$\endgroup$

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.