8
$\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$
0

6 Answers 6

43
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ wow.. nice answer +1. Your answe is better than my one. $\endgroup$
    – Bumblebee
    Sep 26, 2014 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, 2014 at 4:36
  • 5
    $\begingroup$ @Sam You'll have to figure this out yourself. $\endgroup$ Sep 26, 2014 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$ Sep 26, 2014 at 4:44
  • 2
    $\begingroup$ @ThisIsNotAnId You too will have to figure this out yourself. $\endgroup$ Sep 26, 2014 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$
3
  • 18
    $\begingroup$ This is overkill. $\endgroup$ Sep 26, 2014 at 4:21
  • 5
    $\begingroup$ If by "large $n$" you mean "$n > 3$", then, sure.. $\endgroup$
    – Thomas
    Sep 26, 2014 at 14:14
  • $\begingroup$ The OP was looking for a way to prove the statement from scratch, I guess. $\endgroup$
    – user65203
    Nov 29, 2016 at 18:52
6
$\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$
4
$\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$
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$
2
  • 1
    $\begingroup$ This is precisely Nilan's answer. $\endgroup$
    – daniel
    Sep 26, 2014 at 4:32
  • $\begingroup$ Yeah I have just seen. $\endgroup$
    – Ri-Li
    Sep 26, 2014 at 4:32

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.